[C] 백준 11657 타임머신

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

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

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

제출 30800 정답 비율 19%

코드

#include <stdio.h>
#define MAX 1000
#define INF 999999


typedef struct bus {
	int start;
	int end;
	int time;
} BUS;

BUS arr[1000];
int N, M;
int dist[1000];

void main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d", &arr[i].start, &arr[i].end, &arr[i].time);
	}//입력

	dist[1] = 0;
	for (int i = 2; i <= N; i++) dist[i] = INF;
	//거리 초기화

	int cycle = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (dist[arr[j].start] == INF)
				continue;
			//start의 노드에 해당하는 dist 값이 INF이면 pass

			if (dist[arr[j].start] + arr[j].time >= dist[arr[j].end])
				continue;
			//start에서까지에 새로운 time을 추가한 것 >= end까지의 누적 값 이면 pass

			dist[arr[j].end] = dist[arr[j].start] + arr[j].time;
			//두 가지 조건으로 pass되지 않았다면 새로운 dist값으로 갱신

			if (i == N) cycle = 1;
			//음수값으로 인해 시간을 무한히 오래 전으로 되돌릴 수 있는 경우 cycle 값 1
		}
	}//이중for문 종료

	if (cycle == 1) printf("-1");
	else {
		for (int i = 2; i <= N; i++) {
			if (dist[i] == INF) printf("-1\n"); 
			// 해당 도시로 가는 경로가 없는 경우
			else printf("%d\n", dist[i]);
		}
	}

	
}