icpc.me 16763 - CyberFlower Algorithm

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

최단거리로 가는 것과 먹이가 있는 곳에 들러서 먹고 가는 것 중에 어느 경로가 이익인지 구하는 문제입니다. 급식소에는 최대한 한번만 들를 수 있습니다.

그래프 모델링을 잘 한다면 다익스트라로 풀 수 있습니다. 처음에는 최단거리를 구하면 되기 때문에 일반적인 다익스트라를 돌려 줍니다.

우리는 급식소에서 밥을 먹는 과정을 음간선이라고 생각할 수 있습니다. 또, 하나의 급식소만 들러야 하기 때문에 negative cycle도 생기지 않습니다. negative cycle이 생기지 않으니 모델링만 잘 하면!! 다익스트라를 돌릴 수 있습니다.

그래서 그래프 모델링은 어떻게 할까요? 새로운 정점 N’ 을 만듭니다. 그리고 N’ 에서 모든 급식소에 {처음에 구한 최단거리-먹이}를 가중치로 갖는 간선을 연결합니다.

소가 밥을 먹고 N으로 가는 경우에 가장 이익이 되는 경로는 어떤 급식소 x에 가고 나서 가장 빠른 경로로 N으로 가는 경로입니다. 즉, N에서 {최단거리-먹이} 에 해당하는 경로를 만들어 주는 것이 합리적입니다. 굳이 N+1로 나눈 이유는 N+1로 나누면 한 번은 반드시 방문해야 한다는 조건과 음의 사아클 처리가 쉬워지기 때문입니다.

코드를 보도록 하겠습니다.

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define INF (int)1e9+5
using namespace std;
typedef pair<int,int> pii;
const int SZ=50005;
vector<pii> graph[SZ];
int dst1[SZ];
int dst2[SZ];
void dijk(int *dst, int stt){
	for(int i=1;i<stt;i++) dst[i]=INF;
	dst[stt]=0;
	priority_queue<pii> pq;
	pq.push({-dst[stt],stt});
	while(!pq.empty()){
		pii t=pq.top(); pq.pop();
		if(dst[t.ss]!=-t.ff) continue;
		for(pii nxt:graph[t.ss]){
			if(dst[nxt.ff]>dst[t.ss]+nxt.ss){
				dst[nxt.ff]=dst[t.ss]+nxt.ss;
				pq.push({-dst[nxt.ff],nxt.ff});
			}
		}
	}
}
int main(void){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n,m,k; cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		int x,y,z; cin>>x>>y>>z;
		graph[x].pb({y,z});
		graph[y].pb({x,z});
	}
	dijk(dst1,n);
	for(int i=0;i<k;i++){
		int x,y; cin>>x>>y;
		graph[n+1].pb({x,dst1[x]-y});
	}
	dijk(dst2,n+1);
	for(int i=1;i<n;i++){
		cout<<(dst1[i]>=dst2[i]?1:0)<<'\n';
	}
	return 0;
}

백준 16763 Fine Dining