Seletiva IOI 2013

jogo.cpp

// Ivan Carvalho
// Jogo - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define MAX 10010
#define LIMIT 1000000000
#define F first
#define S second
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
vii lista[MAX];
int distancias[MAX],visitado[MAX],resposta=LIMIT;
vector<int> inicios;
int main(){
	int n,m,a,b;
	scanf("%d %d %d %d",&n,&m,&a,&b);
	for(int i=0;i<m;i++){
		int u,v,peso;
		scanf("%d %d %d",&u,&v,&peso);
		lista[u].PB(MP(v,peso));
		lista[v].PB(MP(u,peso));
	}
	for(int i=0;i<a;i++){
		int davez;
		scanf("%d",&davez);
		inicios.PB(davez);
	}
	while(b--){
		for(int i=0;i<=n;i++) visitado[i] = 0;
		int davez;
		scanf("%d",&davez);
		priority_queue<ii, vii, greater<ii> > sssp;
		sssp.push(MP(0,davez));
		while(!sssp.empty()){
			ii atual = sssp.top();
			sssp.pop();
			int vertice = atual.S, percorrido = atual.F;
			if (percorrido >= resposta) break;
			if (visitado[vertice]) continue;
			visitado[vertice] = 1;
			distancias[vertice] = percorrido;
			for(int i=0;i<lista[vertice].size();i++){
				ii proximo = lista[vertice][i];
				sssp.push(MP(percorrido+proximo.S,proximo.F));
			}
		}
		for(int i=0;i<a;i++) {
			if (visitado[inicios[i]]) resposta = min(resposta,distancias[inicios[i]]);
		}
	}
	printf("%d\n",resposta);
	return 0;
}