JOI 2011 本選 「JOI国の買い物事情」 AOJ0562 (Shopping in JOI Kingdom) 解答

dijkstra法やるだけ

#include <bits/stdc++.h>
using namespace std;
 
struct edge{int to,cost;};
typedef pair<int,int> P;
int n,m,k,ans,d[3007],miti[100005][3];
const int INF = 1000000000;
vector<edge> G[3007];
int main(){
    scanf("%d%d%d",&n,&m,&k);
 
    for(int i = 0;i <= n;i++){
        d[i] = INF;
    }
    for(int i = 0;i < m;i++){
        int a,b,l;
        scanf("%d%d%d",&a,&b,&l);
        miti[i][0] = a,miti[i][1] = b,miti[i][2] = l;
        edge tmp = {b,l};
        G[a].push_back(tmp);
        edge tmp2 = {a,l};
        G[b].push_back(tmp2);
    }
    priority_queue<P,vector<P>,greater<P> > que;
    for(int i = 0;i < k;i++){
        int a;
        scanf("%d",&a);
        d[a] = 0;
        que.push(P(0,a));
    }
 
    while(que.size()){
        P q = que.top(); que.pop();
        if(d[q.second] < q.first)continue;
        for(int i = 0;i < G[q.second].size();i++){
            edge es = G[q.second][i];
            if(d[es.to] > q.first + es.cost){
                d[es.to] = q.first + es.cost;
                que.push(P(d[es.to],es.to));
            }
        }
    }
    for(int i = 1;i <= n;i++){
        ans = max(ans,d[i]);
    }
    for(int i = 0;i < m;i++){
        int a =d[miti[i][0]],b = d[miti[i][1]],l = miti[i][2];
        if(a > b)swap(a,b);
        l -= (b-a);
        if(l <= 0)continue;
        ans = max(ans,b+(l+1)/2);
    }
    printf("%d\n",ans);
    return 0;
}