백준 9370 : 미확인 도착지

https://www.acmicpc.net/problem/9370

기본적으로 한 지점에서 다른 지점으로 가는 최단경로가 필요한데 어떤 두 정점을 방문해야 하거나 한 간선을 들려야 한다면

다익스트라 3번으로 최단경로를 구할 수 있다.

start >> n1 -- n2 >> end

는 ① (start->n1) + (n1->n2) + (n2->end) 최단경로와 ②(start->n2) + (n2->n1) + (n1->end) 최단경로를 구할 수 있다.

s를 기준으로 다익스트라 할 경우 s->end 까지 최소비용을 알 수 있다.

그 값이 ① 또는 ② 둘중 하나와 같다면 end 후보지를 만족한다고 볼 수 있다.

※ 그런데, 더 획기적인 방법이 있다!! (시간이 엄청 짧은 사람의 풀이를 보다가 발견하였다.)

만약 가중치가 모두 정수일때 모든 간선의 가중치들을 *2 해주고 n1-n2 사이의 가중치를 -1 해줘서 홀수로 만든다.

이후 다익스트라를 한번해주면 후보지의 가중치가 홀수일때 무조건 n1-n2를 지난 것으로 손쉽게 확인할 수 있다.

-1을 해줄경우 만약 원래 간선기준으로 n1-n2를 지나던 안지나던 최단경로가 같을 경우 무조건 n1-n2 경로를 지나게

할 수 있어 중복경로를 걸러낼 수 있다는 장점이 있다.

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

#include <iostream> #include <vector> #include <queue> #include <algorithm> #define INF 200000000 using namespace std; struct Vertex{ int dist = INF, idx; vector<int> post; vector<pair<int, int>> next; bool operator < (const Vertex &v) const { return dist > v.dist; } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int tc; cin >> tc; while(tc--){ int n, m, t, s, g, h; cin >> n >> m >> t >> s >> g >> h; Vertex vertex[n+1]; for(int i = 1; i <= n; i++){ vertex[i].idx = i; } vector<int> target; while(m--){ int a, b, d; cin >> a >> b >> d; d *= 2; if((a==g&&b==h)||(a==h&&b==g)) d -= 1; vertex[a].next.push_back(make_pair(d, b)); vertex[b].next.push_back(make_pair(d, a)); } while(t--){ int ta; cin >> ta; target.push_back(ta); } priority_queue<Vertex> pq; vertex[s].dist = 0; pq.push(vertex[s]); while(!pq.empty()){ Vertex curVertex = pq.top(); pq.pop(); for(pair<int, int> pa : curVertex.next){ int w = pa.first; int nIdx = pa.second; if(vertex[nIdx].dist > curVertex.dist + w){ vertex[nIdx].dist = curVertex.dist + w; pq.push(vertex[nIdx]); } } } sort(target.begin(), target.end()); for(int tIdx : target){ if(vertex[tIdx].dist % 2 != 0){ cout << tIdx << " "; } } cout << '\n'; } return 0; }