#include #include #define INF (~(1<<31)) #define MAX_N 500 typedef struct { int node; int time; int route[501]; int ridx; }Pos; int N, M; int busTime[MAX_N + 1][MAX_N + 1]; Pos queue[10000]; int front = 0, rear = 0; void enqueue(Pos new) { queue[rear++] = new; } Pos dequeue() { return queue[front++]; } int bfs(int endPoint) { int visited[MAX_N + 1] = { 0 }; for (int i = 0; i <= N; i++) { visited[i] = INF; } front = 0, rear = 0; enqueue((Pos) { 1, 0, { 0 }, 0 }); visited[1] = 0; int minTime = INF; int min_route[501] = { 0 }; while (front < rear) { Pos cur = dequeue(); //printf("cur : %d | time : %d\n", cur.node, cur.time); if (cur.node == endPoint) { if (cur.time < minTime) { //if (memcmp(min_route, cur.route, sizeof(cur.route)) == 0) return INF; // 무한 루프 minTime = cur.time; //memcpy(min_route, cur.route, sizeof(min_route)); //printf("route : "); //for (int i = 0; i < cur.ridx; i++) { // printf("%d ", cur.route[i]); //} //printf("\n"); } //continue; } for (int i = 1; i <= N; i++) { if (busTime[cur.node][i] == INF) continue; //printf("갈수 있는 곳 : %d \n", i); Pos new = { i, cur.time + busTime[cur.node][i], {0}, cur.ridx }; memcpy(new.route, cur.route, sizeof(new.route)); if (new.time < visited[i]) { visited[i] = new.time; new.route[new.ridx++] = new.node; //printf("%d\n", new.ridx); if (new.ridx >= 501) return INF; enqueue(new); } } } if (minTime != INF) { return minTime; } return -1; // 도착 못함 } int main() { scanf("%d %d", &N, &M); int a, b, c; for (int i = 0; i <= MAX_N; i++) { for (int j = 0; j <= MAX_N; j++) { busTime[i][j] = INF; } } for (int i = 0; i < M; i++) { scanf("%d %d %d", &a, &b, &c); busTime[a][b] = c; } for (int end = 2; end <= N; end++) { int res = bfs(end); if (res == INF) { printf("-1\n"); return 0; } printf("%d\n", res); } return 0; } /* 도시 N개 버스 M개 버스 : A(시작) B(도착) C(시간) 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간 */

제출 #102392

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: