Last active
August 14, 2019 15:31
-
-
Save aximov/dc2ce0046b776230eba3dd9d5db6c8c3 to your computer and use it in GitHub Desktop.
ダイクストラ法。ある頂点を始点とする各頂点までの最短経路を求める。負のコストがある場合はベルマンフォード法を使う。マクロ等は https://gist.github.com/aximov/ff8a13ad8aa6c338ec4f88d8970cc1ad
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const int MAX_V = (int)1e5; | |
struct edge { | |
int to, cost; | |
}; | |
typedef pair<int,int> P; // 最短距離、頂点番号 | |
int V; // 頂点数 | |
vector<edge> G[MAX_V]; // グラフ i -> .to by .cost | |
int d[MAX_V]; // s からの最短距離。0-origin に注意 | |
// 頂点 s を始点とする各頂点までの最短経路を求める | |
void dijkstra(int s) { | |
priority_queue<P, vector<P>, greater<P>> que; | |
fill(d, d + V, INF); | |
d[s] = 0; | |
que.push(P(0, s)); | |
while (!que.empty()) { | |
P p = que.top(); que.pop(); | |
int v = p.second; | |
if (d[v] < p.first) continue; | |
REP(i, G[v].size()) { | |
edge e = G[v][i]; | |
if (d[e.to] > d[v] + e.cost) { | |
d[e.to] = d[v] + e.cost; | |
que.push(P(d[e.to], e.to)); | |
} | |
} | |
} | |
} | |
signed main(){ | |
cin.tie(nullptr); | |
ios::sync_with_stdio(false); | |
cin >> V; | |
REP(i,V) { | |
int s; | |
cin >> s; | |
--s; | |
G[i].pb({s,1}); | |
} | |
dijkstra(0); | |
// 例えば頂点 2 までの最短距離は | |
if (d[1] == INF) cout << -1 << endl; | |
else cout << d[1] << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment