[ BOJ 백준 11657번 - 타임머신 ] 해설 및 코드

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

 

목적

음의 가중치가 존재하는 방향 그래프에서 최단 거리를 구하고 음의 사이클이 존재하는지 확인하자.

 

접근법

1. 밸만 포드 알고리즘 연습하라고 만든 문제이다. 따라서 목적에 맞는 알고리즘으로 구현한다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
const int INF=5e6;
 
void solution(){
    int n,m,dist[501],edge[6001][3];
    cin>>n>>m;
    f(i,1,m){
        int a,b,c;cin>>a>>b>>c;
        edge[i][0]=a;
        edge[i][1]=b;
        edge[i][2]=c;
    }
    
    dist[1]=0;f(i,2,n)dist[i]=INF;
    
    f(i,1,n-1)f(j,1,m)if(dist[edge[j][0]]!=INF){
        int tmp=dist[edge[j][0]]+edge[j][2];
        if(dist[edge[j][1]]>tmp)dist[edge[j][1]]=tmp;
    }
    
    f(i,1,m)if(dist[edge[i][0]]!=INF&&dist[edge[i][1]]>dist[edge[i][0]]+edge[i][2]){
        cout<<-1<<'\n';
        return;
    }
    f(i,2,n)cout<<(dist[i]==INF?-1:dist[i])<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    solution();
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.