#include <stdio.h> #include <iostream> #include <vector> #include <queue> using namespace std; vector<pair<int, int>> graph[1010]; vector<int> track[1010]; int d[1010]; int V, E; int lineCnt; void dijkstra(int start) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, start}); d[start] = 0; while(!pq.empty()) { int now = pq.top().second; int nowCost = pq.top().first; pq.pop(); if(nowCost != d[now]) { continue; } for(int i = 0; i < graph[now].size(); i++) { int next = graph[now][i].first; int nextCost = graph[now][i].second; if(nowCost+nextCost < d[next]) { d[next] = nowCost+nextCost; pq.push({d[next], next}); track[next].clear(); track[next].push_back(now); } } } } int main(void) { // freopen("B2211_input.txt", "r", stdin); cin >> V >> E; for(int i = 1; i <= V; i++) { d[i] = 199999999; } for(int i = 1; i <= E; i++) { int from, to, weight; cin >> from >> to >> weight; graph[from].push_back({to, weight}); graph[to].push_back({from, weight}); } dijkstra(1); for(int i = 1; i <= V; i++) { lineCnt += track[i].size(); } cout << lineCnt; for(int i = 1; i <= V; i++) { for(int j = 0; j < track[i].size(); j++) { cout << i << " " << track[i][j]; } cout << "\n"; } return 0; } | cs |
'Baekjoon > Graph' 카테고리의 다른 글
[백준 5719] 거의 최단경로 (Dijkstra) (C/C++) (★★★) (0) | 2020.02.19 |
---|---|
[백준 16681] 등산 (Dijkstra) (C/C++) (★★) (0) | 2020.02.18 |
[백준 1504] 특정한 최단경로 (Floyd-Warshall) (C/C++) (0) | 2020.02.17 |
[백준 1238] 파티 (Floyd-Warshall) (C/C++) (0) | 2020.02.17 |
[백준 1916] 최소비용 구하기 (Dijkstra) (C/C++) (0) | 2020.02.16 |