ダイクストラ法。ある頂点を始点とする各頂点までの最短経路を求める。負のコストがある場合はベルマンフォード法を使う。マクロ等は 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