aoj 0562 - Shopping in JOI Kingdom

問題

問題概要

複数のスタート場所があり、地点までの最短距離を求める。

解法

まず、ダイクストラを利用して、店から他の地点までの最短距離を入れる。このときの店というのは複数ある場合があるので、一番近い店からの距離を求めなければならない。最短距離が求まったら、 次に、辺の間にある家から店までの距離を求める。その時に、店から辺の両端の頂点までの最短距離とその辺のコストで家から店までの距離が求まる。
具体的な計算方法はx - yという辺の間にある家までの距離を求める場合、
{(任意の店からxまでの最短距離) + (任意の店からyまでの最短距離) + (辺xyのコスト)} / 2
で求められる。この式は、ちょうど距離を真ん中にした時点(辺の中間ではない)が時が店からの距離が最長になることを使ってる。またこれはx,yが店でない時に使えるので、どちらかが店の時は別にやる。

ミス

スタート時点がいくつかある時、初めにスタートからの距離を0として、全てqueueに入れておけばうまくいきますね。 隣接行列使う方のダイクストラも初めに、確定した最短距離を入れるところに、0を入れておけば良さそう。 下記のサイトはそうしてると思う。

mudkip-pokemon.blog.so-net.ne.jp

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

const int INF = 1e9;
const int MAX_N = 3010, MAX_E = 10000;
int n, m; //町の数 道路の本数
vector<pair<int, int> > G[MAX_N];//グラフを表す隣接リスト fi:to se:cost
int d[MAX_N]; //sからの最短経路
typedef pair<int, int> P;//firstは最短距離,secondは頂点の番号
int k; vector<int> shop;//店を記録

void dijkstra(void){
    priority_queue<P, vector<P>, greater<P> > que;//firstが小さい順に
    rep(i, n)d[i] = INF;//初期化
    
    //k個のスタート地点を登録
    for(auto i : shop){
        d[i] = 0;
        que.push(make_pair(0, i));
    }
  
    while(!que.empty()){
        auto p = que.top(); que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        for(auto e : G[v]){//e.fi:隣接している頂点の番号 e.se:その頂点までのコスト
            if(d[e.first] > d[v] + e.second){//最短距離が更新されるとき
                d[e.first] = d[v] + e.second;
                que.push(make_pair(d[e.first], e.first));
            }
        }
    }
}

int main(void){
    cin >> n >> m >> k;
    rep(i, m){
        int a, b, l; cin >> a >> b >> l;
        a--; b--;
        G[a].push_back(make_pair(b, l)); G[b].push_back(make_pair(a, l));
    }
    rep(i, k){
        int s; cin >> s; s--;
        shop.push_back(s);
    }
    dijkstra();//店から他の町への最小値を出す
    //道路の間の家も考えた最小値を出す
    double ans = 0.0;
    //x-yのどちらかが店の時
    rep(i, n) ans = max(ans, (double)d[i]);
    //辺の両端の最短距離を利用して、その辺に家がある場合の店からの最長距離を出す
    for (int x = 0; x < n; ++x){
        for(auto y : G[x]){
            if(d[x] == 0 || d[y.first] == 0) continue;
            double tmp = (d[x] + d[y.first] + y.second) / 2.0;//+1は四捨五入用
            ans = max(tmp, ans);
        }
    }
    cout << round(ans) << endl;
    return 0;
}