0w1

Floyd Warshall

GCJ 2017 R1B C. Pony Express ( Floyd Warshall, Dijkstra )

Dashboard - Round 1B 2017 - Google Code Jam題意: T 筆測資。有 N 個城市,用相鄰矩陣表示距離,不保證輸入距離滿足三角不等式。每個城市有一隻馬,用可行走距離 E 和最高速度 S 描述。Q 筆詢問,問 u 到 v 的最少時間。詢問之間不互相影響,而在一筆詢問…

CFR 25 C. Roads in Berland ( Floyd Warshall )

Problem - 25C - Codeforces 先做完一次MSSP之後,對於每個動態操作可以直接詢問每個兩端,是否用了這條邊之後會更好。 注意題目是說額外新增路,所以是不一定要取的。 #include <bits/stdc++.h> using namespace std; const int MAXN = 300 + 3; const int MAXK = 300 + 3;</bits/stdc++.h>…

CFR 295 1B. Greg and Graph ( DP = Floyd Warshall + Reverse Thinking )

Problem - B - Codeforces 如果順著做,逐一破壞。。嗯,看到逐一破壞就可以開始想反著觀察就是逐一增加了。 因為問題是Multiple Source Shortest Path,所以可以馬上想到Floyd Warshall演算法了。 想起以前學長和我提過,為什麼三層迴圈的中繼點要在最外圈…

ABC 22 C - Blue Bird ( Floyd Warshall )

C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder Problem Statement: Given a graph of n ≤ 300 nodes and some edges, find the minimum weight sum of a cycle that starts from 1, goes to some other nodes and end in 1. Basically, we will be…