AOJ 0562 JOI国の買い物事情

JOI本選まで一週間を切っています
動的計画法の問題を安定して解けるようになりたい
解法
dijkstra法使う

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1 << 29;
const int MAX_V = 3000, MAX_E = 100000;
typedef pair<int, int> P;
typedef pair<int, int> EDGE;
vector<EDGE> G[MAX_E];
vector<int> shop;
int V, E, K;
int d[MAX_V];
int main(){
	scanf("%d %d %d", &V, &E, &K);
	fill(d, d + V, INF);
	for(int i = 0; i < E; i++){
		int a, b, l;
		scanf("%d %d %d", &a, &b, &l);
		a--; b--;
		G[a].push_back(EDGE(l, b));
		G[b].push_back(EDGE(l, a));
	}
	priority_queue<P, vector<P>, greater<P> > Q;
	for(int i = 0; i < K; i++){
		int a;
		scanf("%d", &a);
		a--;
		d[a] = 0;
		Q.push(P(0, a));
	}
	while(!Q.empty()){
		P e = Q.top(); Q.pop();
		int dist = e.first;
		int v = e.second;
		if(d[v] < dist) continue;
		for(int i = 0; i < G[v].size(); i++){
			int u = G[v][i].second;
			int dd = G[v][i].first;
			if(dist + dd < d[u]){
				d[u] = dist + dd;
				Q.push(P(d[u], u));
			}
		}
	}
	int ans = 0;
	for(int v = 0; v < V; v++){
		for(int j = 0; j < G[v].size(); j++){
			int l = G[v][j].first;
			int u = G[v][j].second;
			ans = max(ans, (d[v] + d[u] + l + 1) / 2);
		}
	}
	printf("%d\n", ans);
	return 0;
}