第10回日本情報オリンピック 本選 「JOI国の買い物事情」 AOJ0562 (Shopping in JOI Kingdom)

解法：ダイクストラ＋少しの考察。

1. まずダイクストラ法で各町についてショッピングモールまでの最短距離を求める。
2. 次にそれぞれの道について、関数calcで計算する。

関数calcは道の両端の町のショッピングモールまでの最短距離と道の長さからその道の間にあるもっともショッピングモールから遠い点を求めます。

詳細はプログラムソースから察してください。

計算量はO(M log n)とかそこら辺

#include <bits/stdc++.h>

using namespace std;
const int INF = 1000000000;
typedef pair<int,int> P;
struct edge{int to,cost;};
vector<edge> G[3002];
int d[3004];


int n,m,k,l[100003][3],ans;

int calc(int a,int b,int c){
	if(a == b){
		return (a + (c+1)/2);
	}else{
		if(a > b)swap(a,b);
		if(b-a >= c)return b;
		else return (b + (c-(b-a)+1)/2);
	}
}


int main(){
	scanf("%d%d%d",&n,&m,&k);

	for(int i = 0;i < m;i++){
		scanf("%d%d%d",&l[i][0],&l[i][1],&l[i][2]);
		edge tmp = {l[i][1],l[i][2]};
		G[l[i][0]].push_back(tmp);
		edge tmp2 = {l[i][0],l[i][2]};
		G[l[i][1]].push_back(tmp2);
	}
	priority_queue<P,vector<P>,greater<P> >que;
	fill(d,d + n+1,INF);
	for(int i = 0;i < k;i++){
		int t;
		scanf("%d",&t);
		d[t] = 0;
		que.push(P(0,t));
	}
	while(que.size()){
		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));
			}
		}
	}
	for(int i = 1;i <= n;i++){
		ans = max(ans,d[i]);
	}
	for(int i = 0;i < m;i++){
		ans = max(ans,calc(d[l[i][0]],d[l[i][1]],l[i][2]));
	}
	printf("%d\n",ans);
	return 0;
}