[BOJ 11657] 타임머신

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

11657번: 타임머신

 

- 문제 요약

 

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다.

각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는 데 걸리는 시간이다.

시간 C가 양수가 아닌 경우가 있다.

C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.

그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시,..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다.

만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

 

- 알고리즘 정리

 

간선이 음수인 경우도 있으므로 다익스트라가 아닌 벨만 포드로 문제를 풀었습니다.

반복문을 돌리면서 최단거리를 만들어 준 후에, 최단거리가 갱신되는지 아닌지를 확인해서 사이클 여부를 확인해 줍니다.

나머지는 기본적인 벨만 포드 알고리즘 코드와 동일합니다.

https://namu.wiki/w/%EB%B2%A8%EB%A8%BC-%ED%8F%AC%EB%93%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

벨먼-포드 알고리즘 - 나무위키

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MAX 501
#define INF 2100000000
int n,m,a,b,c;
ll dist[MAX];
vector<pair<int,int> >v[MAX];
bool flag;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>a>>b>>c;
		v[a].push_back({b,c});
	}
	for(int i=1;i<=n;i++){
		dist[i]=INF;
	}
	dist[1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=0;k<v[j].size();k++){
				int next=v[j][k].first;
				int cost=v[j][k].second;
				if(dist[j]!=INF&&dist[next]>dist[j]+cost){
					dist[next]=dist[j]+cost;
					if(i==n){
						flag=true;
					}
				}
			}
		}
	}
	if(flag){
		cout<<-1<<'\n';
	}
	else{
		for(int i=2;i<=n;i++){
			cout<<(dist[i]!=INF?dist[i]:-1)<<'\n';
		}
	}
}