문제링크 : https://www.acmicpc.net/problem/11779
문제 접근
- 다익스트라 응용문제
- 다익스트라 개념 참조 : https://dev-jango.tistory.com/26
- 경로를 구하는 조건이 추가됨 > 이전 경로를 추적하기 위해 pre 배열 사용 : 해당 노드에 도착하기 이전 노드
시간복잡도 계산
- 다익스트라 시간복잡도 : O(ElgE)
- 20 * 1e5 = 2e6
인트 계산
- 거리
- 거리가 나올수 있는 최대값 = 모든 도시를 최대 비용으로 거치는경우
- 1000 * e5 = e8 > INT 사용 가능
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; const int inf = 1e8+10; // 시작점에서부터 해당 노드까지의 거리 int dist[1010]; // 인접 간선 리스트 vector<pair<int, int>> adj[1010]; // 이전 노드값 int pre[1010]; int main() { ios::sync_with_stdio(0); cin.tie(0); // 거리 배열 무한값으로 초기화 fill(dist, dist+1010, inf); int N,M; cin >> N >> M; while(M--) { int a,b,c; cin >> a >> b >> c; adj[a].push_back(make_pair(c,b)); } int st, en; cin >> st >> en; // 시작 노드는 거리 0 dist[st] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(dist[st], st)); while(!pq.empty()) { auto eq = pq.top(); pq.pop(); int ec = eq.first; int ei = eq.second; // 같은 노드에 대한 간선 중, 이미 더 작은 값으로 업데이트 된경우 if(dist[ei] != ec) continue; for(auto x : adj[ei]) { int nc = x.first; int ni = x.second; if(dist[ni] > ec + nc) { dist[ni] = ec + nc; pq.push(make_pair(dist[ni], ni)); // 이전 노드값 추가 pre[ni] = ei; } } } cout << dist[en] << '\n'; vector<int> path; int cur = en; while(cur != st) { path.push_back(cur); cur = pre[cur]; } path.push_back(cur); cout << path.size() << '\n'; reverse(path.begin(), path.end()); for(int x : path) cout << x << ' '; return 0; } | cs |
문제유형
- 다익스트라 - 경로
- pre 배열을 사용해서 경로를 추적
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |
|---|---|
| 백준 11657 타임머신 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |
| 백준 11780 플로이드2 풀이(C++/CPP) (0) | 2021.02.08 |
| 백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP) (0) | 2021.02.08 |
| 백준 1786 찾기 쉬운 풀이(C++/CPP) (0) | 2021.02.07 |