[c++] 백준 1865 - 웜홀(벨만-포드 알고리즘)

0. [c++] 백준

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

1. 풀이

벨만-포드 알고리즘을 활용하여 문제를 해결해보았다. 관련 문제들을 해결하기 위해서 다시금 책을 뒤져가며 공부 후에 코드를 완성하긴 하였는데, 이게 확실하게 이해 된 것 같지는 않다.

다양한 문제에 적용을 해보면서 빠르게 이해를 하도록 하자.

2. 소스코드

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 57 58 59 60 61 62 63 64 65 66 67 68

#include<iostream> #include<vector> #include<algorithm> #include<queue>   using namespace std;   //인접 행렬 번호와 가중치를 저장한다. vector<pair<int, int> > adj[501]; const int INF = 1000000007; queue<int> qu;   void checkTimeShift(int N, int src) {     vector<int> upper(N + 1, INF);     bool updated= false;     upper[src] = 0;     //TC-1번 순회한다.     for (int iter = 0; 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) {             cout << "NO" << endl;             break;         }     }     if (updated)         cout << "YES" << endl;           }   int main() {     int TC, N, M, W;     int start, end, time;          cin >> TC;       for(int k=0;k<TC;k++) {         cin >> N >> M >> W;         for (int i = 1; i <= N; i++) {             adj[i].clear();         }         for (int i = 0; i < M; i++) {             cin >> start >> end >> time;             adj[start].push_back({ end, time });             adj[end].push_back({ start, time });         }         for (int i = 0; i < W; i++) {             cin >> start >> end >> time;             adj[start].push_back({ end, -time });         }         checkTimeShift(N, 1);              }              return 0; } Colored by Color Scripter

cs

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.216~236.

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

도움 되셨으면 하트 꾹!