ベルマンフォード法(ABC 061 D問題)

最短距離を求めるアルゴリズム

・各辺(M本)について、「aからbへコストcで結ばれているならば、dist[b]=min(dist[b],dist[a]+c)」というように距離を更新する
・距離の更新はN-1回ループすれば十分(パスは最長でもN-1(閉路がある場合を除く)で、一度の更新でパスが1長くなる)
・O(NM)
・最長距離を求める問題でも、コストに-1をかければ最短距離問題として解ける
・閉路の判定は、N-1回ループした後もう一度更新してみて距離の値が変わるかどうかをみればよい

問題
以下ネタバレ注意

1. ll B[2010], A[2010], C[2010];
2. ll dist[1010];
3. bool negative[1010];
4. int main() {
5. fill(dist, INF);
6. m0(negative);
7. dist[0] = 0;
8. ll N, M; cin >> N >> M;
9. REP(i, M) {
10. ll a, b, c;
11. cin >> a >> b >> c;
12. a--; b--; c = c * (-1);//コストの符号を逆にする
13. A[i] = a; B[i] = b; C[i] = c;
14. }
15. //一回の更でパスの長さを1増やすことになり、(閉路がない限り)パスは最長でN-1なので(N-1)回繰り返せば十分
16. REP(j, N) {
17. REP(i, M) {
18. dist[B[i]] = min(dist[B[i]], dist[A[i]] + C[i]);
19. }
20. //オーバーフロー対策
21. if (dist[N] < -111100000000000) {
22. cout << "inf" << endl;
23. return 0;
24. }
25. }
26.  
27. //もう一度だけ更新してみて、もし距離が変わるなら(長さをいくらでも小さくできるような)閉路があるということ
28. REP(i, M) {
29. if (dist[B[i]] > dist[A[i]] + C[i]) {
30. dist[B[i]] = min(dist[B[i]], dist[A[i]] + C[i]);
31. negative[B[i]] = true;
32. }
33. }
34.  
35. if (dist[N] < -111100000000000) {
36. cout << "inf" << endl;
37. return 0;
38. }
39.  
40. if (negative[N - 1]) {
41. cout << "inf" << endl;
42. }
43. else {
44. cout << dist[N - 1] * (-1) << endl;
45. }
46. }