AOJ0562 JOI 国の買い物事情

解法

---

Dijkstraしてそれぞれの街のショッピングモールまでの最短距離を求めて、
なんといえばいいか、その…
例えば「A街」と「B街」がありました。
「A街」からショッピングモールまでの最短ルートが10でした。
「B街」から(ry の最短ルートは15でした。
これでA街とB街までの道の長さが10だったら、困るじゃん。
で多分これを計算で求める。
ルート = A + ( B - A ) + ( A~B - ( B - A ) ) / 2
なんか図を書いてみたらこうなった。
あとは切り上げ。
nで割るとしたら ( もとの数 + n - 1 ) / n で良い感じに切り上げできる。

ソース

---

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef pair < int , int > Pi;
#define fr first
#define sc second
#define INF ( 1 << 30 )
struct edge{
  int to, cost;
};
vector < edge > info[3001];
int main() {
  int N, M, K;
 
  cin >> N >> M >> K;
  for(int i = 0 ; i < M ; i++ ){
    int a, b, c;
    cin >> a >> b >> c;
    info[a].push_back((edge){ b, c});
    info[b].push_back((edge){ a, c});
  }
 
  int used[3001];
  fill_n( used, 3001, INF);
  priority_queue< Pi , vector< Pi >,greater< Pi > > que;
  for(int i = 0 ; i < K ; i++ ){
    int a;
    cin >> a;
 
    que.push(Pi( 0, a));
    used[a] = 0;
 
    while(!que.empty()){
      Pi p = que.top();
      que.pop();
      for(int j = 0 ; j < info[p.sc].size() ; j++ ){
        edge e = info[p.sc][j];
        if( used[e.to] > p.fr + e.cost ){
          used[e.to] = p.fr + e.cost;
          que.push( Pi( used[e.to], e.to));
        }
      }
    }
  }
 
 
  int ret = 0;
  for(int i = 1 ; i <= N ; i++ ){
    for(int j = 0 ; j < info[i].size() ; j++ ){
      if( used[i] <= used[info[i][j].to]){
        const int java = used[info[i][j].to] - used[i];
        ret = max( ret, used[i] + java + (info[i][j].cost - java + 1) / 2);
      }
    }
  }
  cout << ret << endl;
}