0w1

Dijkstra

CFR 843 D. Dynamic Shortest Path

Problem Description: You are given a directed weighted graph with N nodes and M edges. Q queries follow: OP = 1: Output the shortest path from node 1 to node V. OP = 2: Read C values, the C[i]'th edge should have its weight incremented by …

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

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

CFR 786 B. Legacy ( Dijkstra, Segment Tree )

Problem - B - Codeforces題意: 給一張圖,N 個點,Q 個邊,起點 S。 邊有三種,各自用 u, v / L, R, w 描述: 1. u -> v : 代價 w 2. u -> [ L, R ] : 代價 w 3. [ L, R ] -> u : 代價 w 問所有終點的單源最短路徑,不存在則輸出 -1。資料規模: N, Q ≤ 1e…

CFR 507 E. Breaking Good ( Dijkstra )

Problem - E - Codeforces題意: 給一個無向圖,有些邊是壞掉的。求一個 1 走到 N 的最短路徑,使得此路徑壞掉的邊最少,且路徑外沒壞掉的邊最少。資料規模: The first line of input contains two integers n, m (2 ≤ n ≤ 1e5, ), the number of cities an…

Yuki 160 最短経路のうち辞書順最小 ( Dijkstra )

No.160 最短経路のうち辞書順最小 - yukicoder なんか前にも書いたような感じがするな.. でもちょっとだけ考えた 経路のリカバリーは終点から一つ前のノードを辿るから、始点と終点を裏返して、同じ距離でたどり着ける場合はその一つ前のノードが小さい方で…

CFR 257 1B. Jzzhu and Cities ( Dijkstra )

Problem - B - Codeforces kmjpさんの解法を参考にしました。 kmjp.hatenablog.jp trainのルートを全部あらかじめpqに入れて、もし一直線で着く方が速いならそれが先に出されて、その場でdisを更新しつつcountを上げる、そうでなければ普通にdijkstraする。 …

CFR 198 1B. Jumping on Walls ( PFS )

Problem - B - Codeforces Dijkstraみたいな感じでやればいいね。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXK = 1e5 + 5; int n, k; char w[ 2 ][ MAXN ]; struct State{ int t, x, lv; State( int _t = -1, int _x = -1, in</bits/stdc++.h>…

CFR 20 C. Dijkstra? ( Dijkstra )

Problem - 20C - Codeforces 根本裸題。。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; const int MAXW = 1e6 + 6; typedef long long ll; typedef pair< int, int > pii; typedef pair< ll, int > pli; int n, m;</bits/stdc++.h>…

CFR 329 1B. Biridian Forest ( Shortest Path )

Problem - 329B - Codeforces Let's think about all other trainers try to meet or wait us at the exit. Certainly if one is able to move to the exit before ( or on the same time ) we do, they will battle us. What if not? We will be able to av…

JOI 10 本選 Shopping in JOI Kingdom ( Dijkstra )

Shopping in JOI Kingdom | Aizu Online Judge 店のある町からMSSPをして店のない町から一番近い店への最短経路を計算する。そうしたあと、答えは max{ round( dis[ i ] + dis[ j ] + weight[ i ][ j ] / 2 ) } Ɐ e( i, j ) ∈ E だとわかる。 #include <bits/stdc++.h> usin</bits/stdc++.h>…

JOI 11 本選 Festivals in JOI Kingdom ( MSSP Dijkstra + Kruskal + Doubling LCA )

Festivals in JOI Kingdom | Aizu Online Judge 先に全ての町について、一番近い祭りの距離を計算する。そして、最大全域木をその最短距離に基づき作る( 祭りに近い方からと遠い方から来ても、近い方を取る )とクエリ( u, v )に対しての答えは ( u, lca( u, …

ABC 21 C - 正直者の高橋くん ( Dijkstra + DP )

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder 経路数の計算、dijkstra を一回やって disをたどりながら dpするだけだね。 #include <bits/stdc++.h> using namespace std; const int MAXN = 100 + 2; const int MAXM = 200 + 2; const int MOD = 1e9 + 7;</bits/stdc++.h>…

UVA 10917 Walk Through the Forest ( Dijkstra + DP )

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 11374 Airport Express ( Dijkstra + Route printing )

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