Skip to content

Instantly share code, notes, and snippets.

@aximov aximov/dijkstra.cpp
Last active Aug 14, 2019

Embed
What would you like to do?
ダイクストラ法。ある頂点を始点とする各頂点までの最短経路を求める。負のコストがある場合はベルマンフォード法を使う。マクロ等は https://gist.github.com/aximov/ff8a13ad8aa6c338ec4f88d8970cc1ad
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
You can’t perform that action at this time.