[c++] 백준 11657 - 타임머신(벨만-포드 알고리즘)

0. [c++] 백준  -

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

1. 풀이

음... 벨만-포드 알고리즘을 활용하여서 모드 푼 것처럼 느껴지는데, 54%에서 문제가 해결되질 않는다....

아아아아아아아아 아무리 생각해도 풀리질 않네, 일단 보류하자.

+) 추가적인 제한을 넣어주니 문제를 해결할 수 있었다.

우선 벨만-포드의 완화를 하는 과정에서 upper[here] = INF인 경우 완화에 들어가지 말고 바로 처음으로 돌아가도록 continue를 사용해주었다. 이를 통해 음수 간선을 만나서 값이 줄어드는 것을 방지해주었다.

이것이 가장 핵심이었다.

추가적으로 변경된 점은 a와 b를 이어주는 간선 중 가중치가 가장 작은 간선만이 유일하게 들어가도록 구현을 해주었다.

2. 소스코드

1차 풀이)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include<iostream> #include<vector>   using namespace std;   const int MAX_N = 501; const int INF = 1000000007;   vector<pair<int, int> > adj[MAX_N];   void bellmanFord(int src, int N) {     vector<int> upper(N + 1, INF);     upper[src] = 0;     bool updated = false;     //N번의 완화를 바로 해주자(여기서 updated를 활용해 불필요한 반복을 줄인다.)     for (int iter = 1; iter <= N; iter++) {         updated = false;         for (int here = 1; here <= N; here++) {             for (int i = 0; i < adj[here].size(); i++) {                 int there = adj[here][i].first;                 int cost = adj[here][i].second;                 if (upper[there] > upper[here] + cost) {                     upper[there] = upper[here] + cost;                     updated = true;                 }             }         }         //만일 짧아지지 않았다면         if (!updated) {             break;         }     }       if (updated)         cout << -1 << endl;     else {         for (int i = 2; i <= N; i++)             if (upper[i] == INF)                 cout << -1 << endl;             else                 cout << upper[i] << endl;     } }   int main() {     int N, M;     int A, B, cost;     cin >> N >> M;     for (int i = 0; i < M; i++) {         cin >> A >> B >> cost;         adj[A].push_back({ B,cost });     }     bellmanFord(1, N);       return 0; } Colored by Color Scripter

cs

2차 풀이)

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
const int MAX_N = 501;
const int INF = 1000000007;
 
int edge[501][501];
vector<pair<int, int> > adj[MAX_N];
 
void bellmanFord(int src, int N) {
    vector<int> upper(N + 1, INF);
    upper[src] = 0;
    bool updated = false;
    //N번의 완화를 바로 해주자(여기서 updated를 활용해 불필요한 반복을 줄인다.)
    for (int iter = 1; iter <= N; iter++) {
        updated = false;
        for (int here = 1; here <= N; here++) {
            if (upper[here] == INF)
                continue;
            for (int i = 0; i < adj[here].size(); i++) {
                int there = adj[here][i].first;
                int cost = adj[here][i].second;
                if (upper[there] > upper[here] + cost) {
                    upper[there] = upper[here] + cost;
                    updated = true;
                }
            }
        }
        //만일 짧아지지 않았다면 반복을 종료한다.
        if (!updated) {
            break;
        }
    }
 
    //N번째 차례에서도 완화가 일어났다면, negativeCycle이 존재한다.
    if (updated)
        cout << -1 << endl;
    else {
        for (int i = 2; i <= N; i++)
            if (upper[i] == INF)
                cout << -1 << endl;
            else
                cout << upper[i] << endl;
    }
}
 
int main() {
    int N, M;
    int A, B, cost;
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            edge[i][j] = INF;
 
    //a와 b를 연결해주는 가장 짧은 간선만을 담는다.
    for (int i = 0; i < M; i++) {
        cin >> A >> B >> cost;
        edge[A][B] = min(edge[A][B], cost);
        //adj[A].push_back({ B,cost });
    }
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (edge[i][j] < INF)
                adj[i].push_back({ j, edge[i][j] });
 
 
    bellmanFord(1, N);
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!