# JOI 10 本選 Shopping in JOI Kingdom ( Dijkstra )

Shopping in JOI Kingdom | Aizu Online Judge

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;
}
```