[BOJ/20218] Parity Constraint Shortest Path, c++

🔗 링크

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

20128번: Parity Constraint Shortest Path

https://github.com/jokj624/PS/blob/master/20000-25000/20128.cpp

GitHub - jokj624/PS: BOJ, CodeForces 알고리즘 문제 소스코드

🤯 한줄 후기

술을 홀짝!

🤷 문제

👩‍💻 풀이

간만에 푼 dijkstra 문제!

짝수 최단거리, 홀수 최단거리를 나눠서 구해주는 문제이다.

1번 정점에서 모든 정점으로 다익스트라를 돌릴건데 odd, even 거리를 따로 구해준다.

키포인트는

 

1. 홀수 + 홀수 = 짝수

2. 짝수 + 홀수 = 홀수

3. 짝수 + 짝수 = 짝수

 

현재 정점에서 다른 정점으로 이동할 때 간선의 비용이 홀수인지, 짝수인지 구분해서 각 각 update 해주면 된다.

홀/짝 거리 중 하나라도 update 됐다면 queue에 다시 넣어준다.

💻 코드

//AC
//BOJ 20218 Parity Constraint Shortest Path
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 9223372036854775807
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<pll, int> ppli;
priority_queue<ppli, vector<ppli>, greater<ppli>> pq;
vector<pll> v[101010];
ll odd[101010];
ll even[101010];
bool ck[101010];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N, M, x, y, c;
    cin >> N >> M;
    for(int i=0; i<M; i++) {
        cin >> x >> y >> c;
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
    for(int i=1; i<=N; i++) {
        odd[i] = INF;
        even[i] = INF;
    }
    even[1] = 0;  // 1->1 짝수 최소는 무조건 0
    pq.push({{odd[1], even[1]}, 1});
    while(!pq.empty()) {
        int xx = pq.top().second;
        pq.pop();
        for(auto tmp : v[xx]) {
            ll yy = tmp.first;
            if(tmp.second % 2) {
                int check = 0;
                if(odd[yy] > even[xx] + tmp.second && even[xx] != INF) { // 짝수 + 홀수 = 홀수
                    odd[yy] = even[xx] + tmp.second;
                    check = 1;
                }
                if(even[yy] > odd[xx] + tmp.second && odd[xx] != INF) { // 홀수 + 홀수 = 짝수
                    even[yy] = odd[xx] + tmp.second;
                    check = 1;
                }
                if(check) pq.push({{odd[yy],even[yy]}, yy});
            }
            else {
                int check = 0;
                if(even[yy] > even[xx] + tmp.second && even[xx] != INF) {  // 짝수 + 짝수 = 짝수
                    even[yy] = even[xx] + tmp.second;
                    check = 1;
                }
                if(odd[yy] > odd[xx] + tmp.second && odd[xx] != INF) {  // 짝수 + 홀수 = 홀수
                    odd[yy] = odd[xx] + tmp.second;
                    check = 1;
                }
                if(check) pq.push({{odd[yy], even[yy]}, yy});
            }
        }
    }
    for(int i=1; i<=N; i++) {
        if(odd[i] != INF)   cout << odd[i] << " ";
        else    cout << -1 << " ";
        if(even[i] != INF)  cout << even[i] << " ";
        else    cout << -1 << " ";
        cout << "\n";
    }
    return 0;
}