백준 1753 최단경로 / 다익스트라

1. 다익스트라 2. 힙과 큐 3. 오케이 4. 이것을 사용해서 5. 다익스트라 구현함 6. 순서를 알아야 함 7. 양의 가중치를 가진 그래프에서 가장 가까운 거리를 구하는 것임 8. STL을 사용하지 않고, 구현 가능

#include <cstdio> #include <algorithm> #include <queue> #include <vector> #include <cstring> using namespace std; int v, e, s, x, y, z, d[20002]; vector<vector<pair<int, int>>> vt; int main() { freopen("input.txt", "r", stdin); scanf("%d%d%d", &v, &e, &s); vt.resize(v + 1); for (int i = 0; i < e; i++) { scanf("%d%d%d", &x, &y, &z); vt[x].push_back({ y,z }); } //인접리스트로 그래프를 형성 memset(d, -1, sizeof(d));//거리가 담길 배열 d를 나올 수 없는 수(-1)로 초기화 priority_queue<pair<int, int>> pq;//정보를 담을 힙(거리,정점) pq.push({ 0,s });//시작정점의 정보를 삽입 while (pq.size()) {//pq가 빌 때까지 다익스트라 알고리즘 동작 int here = pq.top().second;//현재 확인하는 정점 int cost = -pq.top().first;//거리(비용) -를 붙이는 이유는 pq를 minheap으로 사용하기 위함 pq.pop(); if (d[here] != -1) continue;//이미 계산되었다면 넘어감 d[here] = cost;//최단거리 정보를 갱신 for (auto it : vt[here]) { int next = it.first;//다음 정점 int acost = -it.second - cost;//누적 된 거리 if (d[next] != -1) continue;//이미 계산되었다면 넘어감 pq.push({ acost,next }); } } for (int i = 1; i <= v; i++) { if (d[i] == -1)puts("INF"); else printf("%d\n", d[i]); }//최단거리 출력 return 0; }