POJ 2394 Checking an Alibi

http://poj.org/problem?id=2394

解法：ダイクストラやるだけ。

JOI予選近いですね・・・

#include <cstdio>
#include <queue>
#include <vector>


using namespace std;

int f,p,c,m;

const int INF = 100000000;
const int MAX_V = 510;
struct edge{ int to,cost;};
typedef pair<int,int> P;
int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
	priority_queue<P,vector<P>,greater<P> > que;
	fill(d,d+V+1,INF);
	d[s] = 0;
	que.push(P(0,s));
	while(!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second;
		if(d[v] < p.first)continue;
		for(int i = 0;i < G[v].size();i++){
			edge e = G[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}



int ko[102]={0};
int main(){
	scanf("%d%d%d%d",&f,&p,&c,&m);
	V = f;
	for(int i = 0;i < p;i++){
		int a1,a2,a3;
		scanf("%d%d%d",&a1,&a2,&a3);
		edge tmp = {a2,a3};
		G[a1].push_back(tmp);
		edge tmp2 = {a1,a3};
		G[a2].push_back(tmp2);
	}
	int ans = 0;
	dijkstra(1);
	for(int i = 1;i <= c;i++){
		int tmp;
		scanf("%d",&tmp);
		if(d[tmp] <= m)ko[ans++]=i;
	}
	printf("%d\n",ans);
	for(int i = 0;i < ans;i++){
		printf("%d\n",ko[i]);
	}
	return 0;
}