JOI 10 本選 Shopping in JOI Kingdom ( Dijkstra )

Shopping in JOI Kingdom | Aizu Online Judge
店のある町からMSSPをして店のない町から一番近い店への最短経路を計算する。そうしたあと、答えは
max{ round( dis[ i ] + dis[ j ] + weight[ i ][ j ] / 2 ) } Ɐ e( i, j ) ∈ E だとわかる。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 3;
const int MAXM = 1e5 + 5;
const int MAXW = 1e3 + 3;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n, m, k;

struct Edge{
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0): u(_u), v(_v), w(_w){}
} es[ MAXM * 2 ];

vector<int> G[ MAXN ];
vector<int> shop;

struct Dijkstra{
    int vis[ MAXN ], dis[ MAXN ];
    void init(){
        memset( dis, INF, sizeof(dis) );
    }
    void solve(){
        priority_queue< pii, vector<pii>, greater<pii> > pq;
        for(int s: shop)
            pq.push( pii( dis[ s ] = 0, s ) );
        while( !pq.empty() ){
            int u = pq.top().second; pq.pop();
            if( vis[ u ] ) continue;
            vis[ u ] = 1;
            for(int vidx: G[ u ]){
                Edge &e = es[ vidx ];
                if( dis[ e.v ] > dis[ e.u ] + e.w ){
                    dis[ e.v ] = dis[ e.u ] + e.w;
                    pq.push( pii( dis[ e.v ], e.v ) );
                }
            }
        }
    }
} dijkstra;

void solve(){
    dijkstra.init();
    dijkstra.solve();
    int ans = 0;
    for(int u = 1; u <= n; ++u)
        for(int vidx: G[ u ]){
            Edge &e = es[ vidx ];
            ans = max( ans, ( dijkstra.dis[ u ] + dijkstra.dis[ e.v ] + e.w + 1 ) / 2 );
        }
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < m; ++i){
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        es[ i ] = Edge( u, v, w );
        es[ m + i ] = Edge( v, u, w );
        G[ u ].push_back( i );
        G[ v ].push_back( m + i );
    }
    for(int i = 0; i < k; ++i){
        int s; scanf("%d", &s);
        shop.push_back( s );
    }
    solve();
    return 0;
}