AOJ 0562 Shopping in JOI Kingdom
解法
まず全店舗からダイクストラして、最寄りの店までの最短距離(dist[i])を求める。
L[i][j](iとjを結ぶ道の距離)>abs(dist[i]-dist[j])ならばその道上の最も遠くなる場所までの距離は
max(dist[i],dist[j])+(L[i][j]-abs(dist[i]-dist[j]))であるから、それを使って更新していく。
(図を書いてみるとわかると思います。日本語下手クソですいません)
ソースコード
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <functional> #include <iostream> using namespace std; typedef pair<int,int> P; #define pu push #define pb push_back #define INF 2000000000 #define fi first #define sec second struct edge{int to,cost;}; int n,m,k; vector<edge> g[3050]; vector<int> shop; int d[3050]; int dist[3050]; int L[3002][3002]; void input() { memset(L,-1,sizeof(L)); fill(dist,dist+3050,INF); cin >> n >> m >> k; for(int i=0;i<m;i++) { int a,b,l; cin >> a >> b >> l; edge in; in.to=b; in.cost=l; g[a].pb(in); in.to=a; g[b].pb(in); L[a][b]=l; L[b][a]=l; } for(int i=0;i<k;i++) { int s; cin >> s; shop.pb(s); } return; } void update() { for(int i=1;i<=n;i++) { dist[i]=min(dist[i],d[i]); } return; } void dijkstra(int s) { fill(d,d+n+1,INF); priority_queue<P,vector<P>,greater<P> > q; d[s]=0; q.push(P(0,s)); while(!q.empty()) { P a=q.top(); q.pop(); if(d[a.sec]<a.fi)continue; for(int i=0;i<g[a.sec].size();i++) { edge e=g[a.sec][i]; if(d[e.to]>d[a.sec]+e.cost) { d[e.to]=d[a.sec]+e.cost; q.push(P(d[e.to],e.to)); } } } update(); return; } int main() { input(); for(int i=0;i<shop.size();i++) { dijkstra(shop[i]); } int ans=0; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { if(L[i][j]==-1)continue; int k=L[i][j]-abs(dist[i]-dist[j]); if(k<=0) { ans=max(ans,max(dist[i],dist[j])); continue; } ans=max(ans,max(dist[i],dist[j])+(k+1)/2); } } cout << ans << endl; return 0; }