[C++] 11779번 최소비용 구하기 2

[C++] 11779번 최소비용 구하기 2

A도시에서 B도시까지 이동할 때 1~3을 구하는 문제입니다.

1. 최소비용

2. 지나온 도시들의 수

3. 지나온 도시 이름

우선순위큐를 이용한 다익스트라로 문제를 해결하였습니다.

1의 경우 - 우선순위 다익스트라를 이용해서 시간초과 없이 해결할 수 있었습니다.

2, 3의 경우 - 경로가 갱신될때 이전의 노드에 대한 정보를 기억해서 도착노드에서

이전노드를 하나씩 확인해서 카운트하고 출력해 주었습니다.

#include #include #include #define MAX_VALUE 987654321 using namespace std; struct pq_data { int node, cost; }; struct compare { bool operator()(pq_data a, pq_data b) { return a.cost < b.cost; } }; int main(int argc, char *argv[]) { int n, m; int start, destination; int now, next, cost; int num; int go; int location; int count = 2; vector city; vector > > v; vector d; vector pre; priority_queue, compare> pq; cin >> n >> m; v.resize(n+1); d.resize(n+1); pre.resize(n+1); fill(d.begin(), d.end(), MAX_VALUE); for(int i=0; i> now >> next >> cost; v[now].push_back({next, cost}); } cin >> start >> destination; d[start] = 0; pq.push({start, 0}); while(!pq.empty()){ now = pq.top().node; cost = pq.top().cost; pq.pop(); for(int i=0; i d[now] + v[now][i].second){ d[next] = d[now] + v[now][i].second; pq.push({next, d[next]}); pre[next] = now; } } if(go == destination){ break; } } cout << d[destination] << endl; location = pre[destination]; city.push_back(destination); while(1){ if(location != start) { city.push_back(location); location = pre[location]; ++count; } else { break; } } city.push_back(start); cout << count << endl; for(int i=city.size()-1; i>=0; --i){ cout << city[i] << " "; } return 0; }

728x90

from http://j3sung.tistory.com/790 by ccl(A) rewrite - 2021-08-28 02:26:51