#define _CRT_SECURE_NO_WARNINGS //dijkstra 1238 파티 #include int cost[1100][1100] = { 0, }; int reverse[1100][1100] = { 0, }; int arr[1100]; int brr[1100]; int chk[1100]; int chk2[1100]; int inf = 1 << 28; int n;//도시 개수=학생 명수 int m;//도로 개수 int d;//도착지 int ans=0; int small()//가장 작은거 뽑아내는 함수 { int min = inf; int index = 0; for (int i = 1; i <= n; i++) { if (arr[i] < min && !chk[i]) { min = arr[i]; index = i; } } return index; } int small2()//가장 작은거 뽑아내는 함수 { int min = inf; int index = 0; for (int i = 1; i <= n; i++) { if (brr[i] < min && !chk2[i]) { min = brr[i]; index = i; } } return index; } int main() { int a, b, c; scanf("%d %d %d", &n, &m, &d); for (int i = 1; i <= 1000; i++) { for (int j = 1; j <= 1000; j++) { if (i == j) cost[i][j] = 0; else cost[i][j] = inf; } } for (int i = 1; i <= m; i++) { scanf("%d %d %d", &a, &b, &c); cost[a][b] = cost[a][b] > c ? c : cost[a][b]; } int start = 2; for (int i = 1; i <= n; i++) { arr[i] = cost[start][i]; } chk[start] = 1; for (int i = 1; i <= n - 2; i++) { int current = small(); chk[current] = 1; for (int j = 1; j <= n; j++) { if (!chk[j]) { if (arr[current] + cost[current][j] < arr[j]) arr[j] = arr[current] + cost[current][j]; } } } //방향 바꿔서 한번 더:2로 가는 최소 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n ; j++) { reverse[i][j] = cost[j][i]; } } for (int i = 1; i <= n; i++) { brr[i] = reverse[start][i]; } chk2[start] = 1; for (int i = 1; i <= n - 2; i++) { int current = small2(); chk2[current] = 1; for (int j = 1; j <= n; j++) { if (!chk2[j]) { if (brr[current] + reverse[current][j] < brr[j]) brr[j] = brr[current] + reverse[current][j]; } } } int ans = 0; for (int i = 1; i <= n; i++) { ans = ans > arr[i] + brr[i] ? ans : arr[i] + brr[i]; } printf("%d", ans); return 0; }

제출 #183811

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: