icpc.me 13936 - CyberFlower Algorithm

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

iron과 coal을 모두 한번씩 들리면서 밟을 수 있는 섬의 최소값을 구하는 문제입니다. 저번에 올렸던 fine dining 문제처럼 다익스트라를 잘 돌리면 풀릴거라 생각했지만 풀이가 미묘하게 다릅니다.

다익스트라만을 이용하여 풀기에는 문제가 있습니다. 이미 밟았던 경로를 다시 밟는 경우 처리가 어려워지기 때문이죠. 그렇다면 어떻게 풀어야 할까요?

대략적인 알고리즘은 다음과 같습니다.

모든 노드에 대하여 가장 가까운 iron까지의 거리를 구합니다. 잘 생각해보면 bfs 한번으로 가능합니다.
같은 방식으로 모든 노드에 대하여 가장 가까운 coal까지의 거리를 구합니다.
1에서 모든 노드까지의 최단거리를 다익스트라를 이용하여 구합니다.
1,2,3 에서 구한 거리들의 합 중에서 최솟값을 구합니다.

위와 같은 알고리즘으로 코드를 구현한다면 이미 밟았던 경로를 다시 밟는 걱정을 할 필요가 없습니다.
만약 어떤 경로를 구했는데 그 경로가 이미 밟았던 경로를 다시 밟는 경로라면 다른 섬에서 가는 동일한 경로(하지만 밟은 지점을 다시 밟지는 않는)가 반드시 존재합니다.

방향이 있는 그래프이고 bfs를 돌리는 그래프는 원래 그래프의 역간선으로 이루어져 있음에 주의합시다.

#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define INF (int)1e9+5
using namespace std;
typedef pair<int,int> pii;
const int SZ=100005;
vector<pii> graph[SZ];
vector<int> bfs_graph[SZ];
vector<int> iron, coal;
int dst1[SZ];
int dst2[SZ];
int dst3[SZ];
int n;
void dijk(int *dst, int stt){
	for(int i=1;i<=n;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[t.ss]<INF && dst[nxt.ff]>dst[t.ss]+nxt.ss){
				dst[nxt.ff]=dst[t.ss]+nxt.ss;
				pq.push({-dst[nxt.ff],nxt.ff});
			}
		}
	}
}
void bfs(vector<int> &vv,int *dst){
	for(int i=1;i<=n;i++) dst[i]=INF;
	queue<int> q;
	for(int x:vv){
		dst[x]=0;
		q.push(x);
	}
	while(!q.empty()){
		int f=q.front(); q.pop();
		for(int nxt:bfs_graph[f]){
			if(dst[nxt]!=INF) continue;
			dst[nxt]=dst[f]+1;
			q.push(nxt);
		}
	}
}
int main(void){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int m,k; cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		int x; cin>>x;
		iron.pb(x);
	}
	for(int i=0;i<k;i++){
		int x; cin>>x;
		coal.pb(x);
	}
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		for(int j=0;j<x;j++){
			int y; cin>>y;
			graph[i].pb({y,1});
			bfs_graph[y].pb(i);
		}
	}
	dijk(dst1,1);
	bfs(iron,dst2);
	bfs(coal,dst3);
	int ans=INF;
	for(int i=1;i<=n;i++){
		if(dst1[i]<INF && dst2[i]<INF && dst3[i]<INF){
			ans=min(ans,dst1[i]+dst2[i]+dst3[i]);
		}
	}
	if(ans>=INF) cout<<"impossible";
	else cout<<ans;
	return 0;
}

백준 13936 Iron and Coal