#include #define INF (~(1<<31)) #define MAX_N (800+1) typedef struct { int x; int cost; int visited_index; // 0 : 아예 못 찾음, 1 : v1, 2 : v2, 3 : 다찾음 }Pos; int N, E; int v1, v2; int map[MAX_N][MAX_N]; int visited[MAX_N][4]; Pos queue[MAX_N * MAX_N]; int front = 0, rear = 0; void enqueue(Pos new) { queue[rear++] = new; } Pos dequeue() { return queue[front++]; } int bfs(int start, int end) { for (int i = 1; i <= N; i++) { for (int j = 0; j <= 3; j++) { visited[i][j] = INF; } } visited[start][0] = 0; enqueue((Pos) { start, 0, 0 }); int min_cost = INF; while (front < rear) { Pos cur = dequeue(); //printf("cur : %d | cost : %d | vi : %d\n", cur.x, cur.cost, cur.visited_index); if (cur.cost > min_cost) continue; if (cur.x == v1 && cur.visited_index != 3 && cur.visited_index != 1) { if (cur.visited_index == 0) cur.visited_index = 1; else if (cur.visited_index == 2) cur.visited_index = 3; } if (cur.x == v2 && cur.visited_index != 3 && cur.visited_index != 2) { if (cur.visited_index == 0) cur.visited_index = 2; else if (cur.visited_index == 1) cur.visited_index = 3; } //printf("cur : %d | cost : %d | vi : %d\n", cur.x, cur.cost, cur.visited_index); if (cur.x == end && cur.visited_index == 3) { if (cur.cost < min_cost) min_cost = cur.cost; continue; } for (int i = 1; i <= N; i++) { if (map[cur.x][i] != 0 && cur.cost < visited[i][cur.visited_index] ) { Pos new = { i, cur.cost + map[cur.x][i], cur.visited_index }; enqueue(new); visited[new.x][new.visited_index] = new.cost; } else { //printf("%d %d\n", map[cur.x][i] != 0, visited[i][cur.visited_index]); } } } if (min_cost != INF) return min_cost; return -1; } int main() { scanf("%d %d", &N, &E); for (int i = 0; i < E; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); map[a][b] = c; map[b][a] = c; } scanf("%d %d", &v1, &v2); printf("%d\n", bfs(1, N)); return 0; } /* 1번 정점부터 N번까지 최단거리 두 정점은 반드시 통과 반드시 최단경로 but 재방문 가능 */

제출 #34648

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: