백준: Class 4 - 1865, 11657: 벨만 포드 알고리즘

</br> 웜홀 문제를 보니 나올 게 나왔다 싶더라
음수 가중치일 때는 다익스트라를 못쓰고 벨만 포드를 써야 한다고 알고만 있고, 해당 알고리즘은 모르는 상태이므로 정리하도록 하자
</br>

벨만 포드 알고리즘

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220796963742 위 블로그를 보고 개인 이해용으로 정리합니다

벨만 포드 알고리즘은 시간 복잡도 O(VE)로, 루프를 V-1번 돌리며 거리를 계속 업데이트한다(k-1번째 루프에선 최대 k-1개 간선을 가진 최단 경로를 구한다).

그런데 음의 가중치가 있으므로, 가중치의 합이 음수인 사이클이 있다면 그 사이클을 계속 돌면 계속 음수가 되고 무한루프가 될 것이다. 따라서 얘네를 신경 써 줘야 한다.

for(i : 0 to V-1 + 1){  // 마지막 1: 음의 사이클 확인
  for(j : 0 to V){
    for(j와 연결된 노드들){
      if(dist[j] != INF && dist[노드] > dist[j] + j와 노드의 가중치){
        dist[노드] = dist[j] + j와 노드의 가중치; // 업데이트
        if( i == V-1 ) 음의 사이클 존재
      }
    }
  }
}

생각보다 간단하네
바로 웜홀을 풀어 보자
</br>

1865: 웜홀

https://www.acmicpc.net/problem/1865

bool func(int n){
    for(int i = 1; i <= n; i++){
        dist[i] = 5000001;
    }
    dist[0] = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= n; k++){
                if( graph[j][k] == 10000 ) continue;
                if( dist[j] != 5000001 && dist[k] > dist[j] + graph[j][k] ){
                    dist[k] = dist[j] + graph[j][k];
                    if( i == n ){
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

// in main()
    while( tc-- ){
        int n, m, w;
        cin >> n >> m >> w;
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n; j++){
                graph[i][j] = 10000;
            }
        }
        for(int i = 0; i < m; i++){
            int s, e, t;
            cin >> s >> e >> t;
            graph[s][e] = min(graph[s][e], t);
            graph[e][s] = min(graph[e][s], t);
        }
        for(int i = 0; i < w; i++){
            int s, e, t;
            cin >> s >> e >> t;
            graph[s][e] = min(graph[s][e], -t);
        }
        for(int i = 1; i <= n; i++){
            graph[0][i] = 0;
        }
        if( func(n) ) cout << "YES\n";
        else cout << "NO\n";
    }

와.. 많이 틀렸다
일단 입력 받을 때 각 가중치는 최솟값으로만 저장하고
이 문제는 컴포넌트가 다 연결되었다는 보장이 없어서, 0번째 노드를 추가해서 0번째에서 다른 모든 노드들로 갈 수 있는 간선들을 추가하고, 음의 사이클이 있는지 확인했다.
</br>

11657: 타임머신

https://www.acmicpc.net/problem/11657

bool func(int n){
    for(int i = 1; i <= n; i++){
        dist[i] = 1e18;
    }
    dist[1] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < edges.size(); j++){
            int s = get<0>(edges[j]);
            int e = get<1>(edges[j]);
            int t = get<2>(edges[j]);
            if( dist[s] != 1e18 && dist[e] > dist[s] + t ){
                dist[e] = dist[s] + t;
                if( i == n ) return true;
            }
        }
    }
    return false;
}

// in main()
    for(int i = 0; i < m; i++){
        int s, e, t;
        cin >> s >> e >> t;
        edges.push_back(make_tuple(s, e, t));
    }
    if( func(n) ) cout << -1 << endl;
    else{
        for(int i = 2; i <= n; i++){
            if( dist[i] != 1e18 ) cout << dist[i] << '\n';
            else cout << -1 << '\n';
        }
    }

찾아보니 그냥 엣지 입력 받은 그대로 사용하는 것도 있던데 이게 더 간단해 보여서 그렇게 해 봤다
이 문제는 위에 웜홀보단 쉽다. 그냥 1에서 시작해서 음의 사이클 있으면 -1, 아니면 거리 출력해주면 된다.
그런데, 보통 dist를 초기화 할 때 V*(E의 최댓값)으로 하는데 그렇게 하니까 오답이 나왔다.
찾아 보니 벨만 포드 알고리즘이 최소값을 계속 갱신하기 때문에, 지금 문제가 정점 500개, 간선 6000개, 간선 최솟값 -10000면 500*600*(-10000) = -3000000000으로 언더플로우가 난다고 한다.
long long으로 선언합시다
</br>

---

어렵구나
</br>