[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]);
}
}
}
Author And Source
이 문제에 관하여([C] 백준 11657 타임머신), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@z00m__in/C-백준-11657-타임머신저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)