【AOJ ALDS1_12】C: Graph Ⅱ - Single Source Shortest Path Ⅱ
問題
最短経路 | アルゴリズムとデータ構造 | Aizu Online Judge
方針
- 隣接行列を用いたダイクストラ法はグラフG=(V, E)においてとなる.
- 今回はノード数がであるので, 隣接リストを使った実装を行う.
- 隣接リストでグラフを表現し, 二分ヒープ(priority_queue)を用いることで飛躍的に高速化することができる.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define ALL(v) v.begin(), v.end() #define mp make_pair #define INF 1e9 #define MAX 10000 using namespace std; typedef pair<int, int> pii; int n; // pair.first : 距離 // pair.second : 頂点 vector<pii> node[MAX]; bool root[MAX]; int d[MAX]; void dijkstra(){ priority_queue<pii> pq; rep(i, MAX){ d[i] = INF; root[i] = false; } d[0] = 0; pq.push(mp(0, 0)); while(!pq.empty()){ pii p = pq.top(); pq.pop(); int u = p.second; root[u] = true; if(d[u] < p.first * -1) continue; rep(i, node[u].size()){ int v = node[u][i].first; if(root[v]) continue; if(d[v] > d[u] + node[u][i].second){ d[v] = d[u] + node[u][i].second; pq.push(mp(d[v] * -1, v)); } } } } signed main(){ cin >> n; int u, k, v, c; rep(i, n){ cin >> u >> k; rep(j, k){ cin >> v >> c; node[u].pb(mp(v, c)); } } dijkstra(); rep(i, n){ cout << i << " " << (d[i] == INF?-1:d[i]) << endl; } }