BOJ 11657 타임머신

1 개요

BOJ 11657 타임머신

• 백준 온라인 저지 11657번 문제
• BOJ 32단계

2 C++

C++

Copy

#include <bits/stdc++.h>
#include <limits.h>
#define INF LONG_MAX
using namespace std;
int N, M;
vector<pair<long,long>> G[501];

bool bellmanFord(int start, int end, vector<long> &dist){
    dist[start] = 0;
    for(int i=1; i<=end; i++){
        for(int x=1; x<=end; x++){
            if(dist[x] == INF) continue;
            for(auto &el : G[x]){
                long nx = el.first;
                long ncost = el.second;
                if(dist[nx] > dist[x] + ncost) {
                    dist[nx] = dist[x] + ncost;
                    if(i == end) return false;
                }
            }
        }
    }
    return true;
}

void solve() {
    vector<long> dist(N+1,INF);
    if(!bellmanFord(1, N, dist)) {
        cout << -1;
        return;
    }
    for(int i=2; i<=N; i++) {
        cout << (dist[i]==INF ? -1 : dist[i]) << '\n';
    }
}

int main(){
    cin >> N >> M;
    int A, B, C;
    for(int i=0; i<M; i++){
        cin >> A >> B >> C;
        G[A].push_back({B,C});
    }
    solve();
}