백준 20128(Parity Constraint Shortest Path)

www.acmicpc.net/problem/20128

20128번: Parity Constraint Shortest Path

 

1번 정점에서 다른 모든 정점까지 이동하는데, 그 경로의 비용이 짝수인 최소비용, 홀수인 최소비용을 출력하는 문제이다. 

 

우선 다익스트라를 안다면 딱봐도 다익스트라일 수 있겠다라는걸 알 수 있다. 

 

일단 문제가 좋았다 

 

다익스트라를 푼지도 오래되었고, 경로의 값이 짝수이려면 어떻게 해야할지 홀수이려면 어떻게 해야할지 생각하는 과정에서 이해가 많이 는것같은 기분 

 

처음에는 홀수가 되려면 짝수에서 홀수를 더하고 홀수에서 짝수를 더하는 방식으로 생각을 하였다. 하지만 이건 내 두뇌의 사고범위를 벗어나서 다른 방법은 없을까 고민하였다. 

 

그냥 애초에 두 종류dist[]배열을 만들어서 홀수 짝수를 다르게 관리할 수 있지 않을까 

 

다익스트라와 같은 방법으로 돌아가되 짝수 홀수 두가지로 돌리면 된다. 

 

아 그리고 앞으로 갱신하기 위해서 확인하는 값이 

이미 존재하는 홀수 값, 짝수 값보다 크면 컨티뉴로 쓸데없는 행동을 막아준다.

 

그리고 해결이 안되어서 학회 슬랙에 green55님에게 도움을 받았는데 이 과정에서 한가지 더 깨달은게 있다. 

다익스트라는 항상 최소로만 최신화를 해준다. 당연한 소리겠지만 

 

solve(){

 

if(dis != ~~ ) continue 랑 if(dis > ~~ ) continue 다익스트라에서는 동치라고 볼수있지 않을까 

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 100005
#define INF 1e18

long long odd_d[MAX];
long long even_d[MAX];
int N, M;
vector<pair<long long, int> > v[MAX];

void solve() {
	even_d[1] = 0;
	priority_queue<pair<long long, int> > pq;
	pq.push(make_pair(0,1));
	while (!pq.empty()) {
		int current = pq.top().second;
		long long dis = -pq.top().first;
		pq.pop();

		if (dis != even_d[current] && dis != odd_d[current])continue;
		for (int i = 0; i < v[current].size(); i++) {
			int next = v[current][i].second;
			long long nextdis = dis + v[current][i].first;

			if (nextdis % 2 == 0) {
				if (nextdis < even_d[next]) {
					even_d[next] = nextdis;
					pq.push(make_pair(-nextdis, next));
				}
			}
			else {
				if (nextdis < odd_d[next]) {
					odd_d[next] = nextdis;
					pq.push(make_pair(-nextdis, next));
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		odd_d[i] = INF;
		even_d[i] = INF;
	}
	for (int i = 1; i <= M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(c, b));
		v[b].push_back(make_pair(c, a));
	}
	solve();
	for (int i = 1; i <= N; i++) {
		if (odd_d[i] == INF) {
			cout << -1 << " ";
		}
		else {
			cout << odd_d[i] << " ";
		}
		if (even_d[i] == INF) {
			cout << -1 << "\n";
		}
		else {
			cout << even_d[i] << "\n";
		}
	}
}