백준 11657 타임머신 쉬운 풀이(C++/CPP)

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

문제 접근

• 벨만포드 기본 문제 : https://dev-jango.tistory.com/28

시간복잡도 계산

• 모든 간선을 : O(E)
• 노드의 개수만큼 반복 : O(V)
• O(V*E)

인트 계산

• 거리의 최대값
  • 최악의 경우 노드 개수(V) * 간선 개수(E) * 최대 비용
  • 500 * 6000 * 1e4 = 3e10
  • long long 사용

코드

#include <iostream>
#include <tuple>
#include <vector>
 
using namespace std;
typedef tuple<int, int, int> ti3;
typedef long long ll;
 
const int inf = 1e8+10;
 
// 거리배열 생성
ll dist[510];
ti3 edge[6010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E; cin >> V >> E;
    fill(dist, dist+510, inf);
    
    for(int i=0; i<E; i++){
        int a,b,c; cin >> a >>b >> c;
        edge[i] = {a,b,c};
    }
    
    // 시작노드 0으로 초기화
    dist[1] = 0;
    
    // 모든 간선을 노드 갯수만큼 반복
    for(int j=0; j<V; j++) {
        for(int i=0; i<E; i++) {
            int a,b,c; tie(a,b,c) = edge[i];
            
            // 아직 거치지 않은 점일경우
            if(dist[a] == inf) continue;
            // a점을 거친 경우 거리가 더 작아질경우
            if(dist[b] > dist[a] + c) dist[b] = dist[a] + c;
        }
    }
    
    // 사이클 확인
    for(int i=0; i<E; i++) {
        int a,b,c; tie(a,b,c) = edge[i];
        
        if(dist[a] == inf) continue;
        // a점을 거친 후 거리가 작아질경우 사이클
        if(dist[b] > dist[a] + c) {
            cout << -1 << '\n';
            return 0;
        }
    }
    
    for(int i=2; i<=V; i++) {
        if(dist[i] == inf) cout << -1 << '\n';
        else {
            cout << dist[i] << '\n';
        }
    }
    
    return 0;
}