UVa Online Judge 用 Dijkstra 求一次從家裡到各個點的單源最短路徑，則所求是公司到家的路徑數，可走的有向邊只存在於滿足 DIjkstra 求出的 dis[ v ] v，很明顯是個 DAG，用 DP 隨便處理就行了。 #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const i</int,></bits/stdc++.h>…

UVa Online Judge 從起點和從終點各做一次單源最短路徑，並紀錄pre 陣列方便打印最短路徑。因為經濟線只能用一次，所以枚舉所有可以用的經濟線，還有一次完全不用經濟線的情況，比較哪個最好。時間複雜度 O( M lg N + K ) #include <bits/stdc++.h> using namespace std; ty</bits/stdc++.h>…

題目的圖論模型是要求將儘量少的點標記，使得刪除任意一點後每個聯通分量有至少一個被標記的點。 我們要發現一般來說標記在割點上不會比較好，而且在同一個點雙連通分量上標記兩個以上的點是無意義的。再說如果一個點雙連通分量含兩個以上的割點，我們可以不…