0. [c++] 백준 - |
https://www.acmicpc.net/problem/1504
1. 풀이 |
이번 풀이에서는 다익스트라와 벨만-포드 알고리즘을 모두 활용하여 보았다. 우씨, 처음에 벨만-포드 알고리즘을 활용하여 문제를 해결해보았는데, 3가지 경우로 나누어서 따로 저장해놓은 int Distance[5] 배열에 1->viaA, 1->viaB ... 등을 저장하여 문제를 풀이하는 방법을 구현해보았다.
근데 여기서 문제는 내가 생각하기에는 정답이 맞는데 자꾸 틀렸습니다가 출력이 되었다.
아아아아아아
그래서 다른 풀이를 찾아보았는데, vector을 통으로 반환하여 이를 활용하는 풀이었었는데, 이렇게 푸니 정답을 받기는 하였다.
도대체 무엇이 문제였던거려나.
2. 소스코드 |
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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | #include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; vector<pair<int, int> > adj[801]; const int INF =987654321; //bool Possible; int Distance[5]; //벨만-포드 방식 vector<int> shortestLength(int N, int viaA, int viaB, int src) { /*if (!Possible) return;*/ vector<int> upper(N + 1, INF); bool updated = false; upper[src] = 0; for (int iter = 0; iter < N; iter++) { updated = false; for (int here = 1; here <= N; here++) for (int i = 0; i < adj[here].size(); i++) { int there = adj[here][i].first; int cost = adj[here][i].second; //더 짧은 거리로 수정한다. if (upper[there] > upper[here] + cost) { updated = true; upper[there] = upper[here] + cost; } } //만일 이번 차례에 단축이 되지 않았다면, 반복을 종료 if (!updated) break; } //if (src == 1) { // Distance[0] = upper[viaA]; // Distance[1] = upper[viaB]; //} //else if (src == viaA) { // Distance[4] = upper[viaB]; //} //else if(src == N){ // Distance[2] = upper[viaA]; // Distance[3] = upper[viaB]; //} return upper; } //다익스트라 bool visited[20001]; vector<int> dijkstra(int N, int src) { vector<int> dist(N+1, INF); dist[src] = 0; priority_queue<pair<int, int> > pq; pq.push(make_pair(0, src)); while (!pq.empty()) { int cost = -pq.top().first; int here = pq.top().second; pq.pop(); //만약 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 지금 꺼낸 것을 무시한다. if (dist[here] < cost) continue; //인접한 정점들을 모두 검사한다. for (int i = 0; i < adj[here].size(); i++) { int there = adj[here][i].first; int nextDist = cost + adj[here][i].second; //더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다. if (dist[there] > nextDist) { dist[there] = nextDist; pq.push(make_pair(-nextDist, there)); } } } return dist; } int main() { int N, E; int a, b, cost; cin >> N >> E; for (int i = 0; i < E; i++) { cin >> a >> b >> cost; adj[a].push_back({ b,cost }); adj[b].push_back({ a,cost }); } /*int node1, node2; cin >> node1 >> node2; vector<int> result = dijkstra(N, 1); vector<int> temp1 = dijkstra(N, node1); vector<int> temp2 = dijkstra(N, node2);*/ ////두 가지 경우 ////1. 1 -> node1 -> node2 -> N ////2. 1 -> node2 -> node1 -> N //int answer = min({ result[node1] + temp1[node2] + temp2[N], result[node2] + temp2[node1] + temp1[N] }); //if (answer >= INF || answer < 0) // cout << -1 << "\n"; //else // cout << answer << "\n"; //return 0; int viaA, viaB; cin >> viaA >> viaB; vector<int> v1 = shortestLength(N, viaA, viaB, 1); vector<int> v2 = shortestLength(N, viaA, viaB, viaA); vector<int> v3 = shortestLength(N, viaA, viaB, viaB); int ret = 0; ret = min(v1[viaA] + v2[viaB] + v3[N], v1[viaB] + v3[viaA] + v2[N]); if (ret >= INF || ret < 0) cout << -1 << endl; else cout << ret << endl; return 0; } | cs |
3. 참고 |
주석된 부분(출력 관련하여서 조금 참조하였다.)
질문이나 지적 있으시면 댓글로 남겨주세요~
도움 되셨으면 하트 꾹!
728x90
반응형
'<백준> > |C++| hard' 카테고리의 다른 글
| [c++] 백준 9248 - Suffix Array(맨버와 마이어스의 알고리즘, LCP Array 계산의 단축) (0) | 2019.06.07 |
|---|---|
| [c++] 백준 11657 - 타임머신(벨만-포드 알고리즘) (0) | 2019.05.29 |
| [c++] 백준 1865 - 웜홀(벨만-포드 알고리즘) (0) | 2019.05.28 |
| [c++] 백준 1753 - 최단경로(다익스트라, dijkstra, priority queue, BFS) (0) | 2019.05.24 |
| [c++] 백준 3665 - 최종 순위(그래프 정렬하기) (0) | 2019.05.15 |