백준 11657 - 타임머신(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11657

11657번: 타임머신

밸만 포드 알고리즘을 이용해 푸는 문제입니다.

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N, M;
vector<pair<P, int>> connect;
long long Distance[501];

void Bellman_Ford(){
    Distance[1] = 0;
    for(int i = 1; i <= N - 1; i++){
        for(int j = 0; j < connect.size(); j++){
            int x = connect[j].F.F;
            int y = connect[j].F.S;
            int cost = connect[j].S;
            if(Distance[x] == INF) continue;
            if(Distance[y] > Distance[x] + cost){
                Distance[y] = Distance[x] + cost;
            }
        }
    }
    for(int i = 0; i < connect.size(); i++){
        int x = connect[i].F.F;
        int y = connect[i].F.S;
        int cost = connect[i].S;
        if(Distance[x] == INF) continue;
        if(Distance[y] > Distance[x] + cost){
            cout << "-1" << "\n";
            return;
        }
    }
    for(int i = 2; i <= N; i++){
        if(Distance[i] == INF) cout << "-1" << "\n";
        else cout << Distance[i] << "\n";
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        Distance[i] = INF;
    }
    Bellman_Ford();
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y, cost;
        cin >> x >> y >> cost;
        connect.push_back({{x,y}, cost});
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요