#include #include using namespace std; #define INF 99999999 typedef struct Node { int v; int w; }Node; int g_V, g_E; vector g_G[20001]; // 그래프 int g_Dijkstra_G[20001]; // 시작 정점에 대한 다른 정점까지의 최소 값 int g_Check_G[20001]; // 각 정점에 대한 조사 여부 확인 int g_V_Num; // 현재 정점 Node g_MinHeap[600002]; // 우선순위 큐(최소 힙) int g_Index_MinHeap = 1; bool isEmptyHeap(); Node PopHeap(); void PushHeap(Node node); int main() { ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // Coding Area cin >> g_V >> g_E; cin >> g_V_Num; for(int i = 0; i < g_E; i++) { int u, v, w; cin >> u >> v >> w; g_G[u].push_back({v, w}); } for(int i = 1; i <= g_V; i++) { g_Dijkstra_G[i] = INF; } for(int i = 1; i <= 600001; i++) { g_MinHeap[i] = {0, INF}; } // 다익스트라 알고리즘(feat BFS) g_Dijkstra_G[g_V_Num] = 0; PushHeap({g_V_Num, 0}); while(!isEmptyHeap()) { g_V_Num = PopHeap().v; if(g_Check_G[g_V_Num]) continue; g_Check_G[g_V_Num] = 1; for(int i = 0; i < (int)g_G[g_V_Num].size(); i++) { int curr_V = g_V_Num; int next_V = g_G[g_V_Num][i].v; int w = g_G[g_V_Num][i].w; if(g_Dijkstra_G[curr_V] + w < g_Dijkstra_G[next_V]) g_Dijkstra_G[next_V] = g_Dijkstra_G[curr_V] + w; PushHeap(g_G[g_V_Num][i]); } } for(int i = 1; i <= g_V; i++) { if(g_Dijkstra_G[i] == INF) cout << "INF" << "\n"; else cout << g_Dijkstra_G[i] << "\n"; } // return 0; } bool isEmptyHeap() { return (g_Index_MinHeap <= 1); } Node PopHeap() { int index = 1; int flag = 1; Node ret = g_MinHeap[1]; g_MinHeap[1] = g_MinHeap[--g_Index_MinHeap]; g_MinHeap[g_Index_MinHeap] = {0, INF}; Node tmp = g_MinHeap[index]; while(index < g_Index_MinHeap) { if(g_MinHeap[index << 1].w < g_MinHeap[(index << 1) + 1].w) { if(tmp.w > g_MinHeap[index << 1].w) { g_MinHeap[index] = g_MinHeap[index << 1]; index = (index << 1); } else { flag = 0; break; } } else { if(tmp.w > g_MinHeap[(index << 1) + 1].w) { g_MinHeap[index] = g_MinHeap[(index << 1) + 1]; index = (index << 1) + 1; } else { flag = 0; break; } } } if(flag) { g_MinHeap[index >> 1] = tmp; } else { g_MinHeap[index] = tmp; } return ret; } void PushHeap(Node node) { int index = g_Index_MinHeap; g_MinHeap[g_Index_MinHeap++] = node; Node tmp = g_MinHeap[index]; while(index > 1) { if(tmp.w < g_MinHeap[index >> 1].w) { g_MinHeap[index] = g_MinHeap[index >> 1]; index = (index >> 1); } else break; } g_MinHeap[index] = tmp; }

제출 #152626

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: