ferinの競プロ帳

競プロについてのメモ

AOJ0562 JOI国のお買い物事情

問題ページ
JOI 国の買い物事情 | Aizu Online Judge

解法

最短経路問題で始点が複数あるパターンなので始点をまとめる架空の頂点をつくってやればdijkstra一回で各頂点への最短距離がわかる。各頂点への最短距離がわかっていれば各辺のどの位置が最短距離が最長になる点なのか計算できる。その点の中で最長のものを答えとして出力する。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

struct edge{int to, cost;};

int n, d[3010], m, k, s[3010];
vector<edge> g[3010];

void dijkstra() {
  priority_queue<PII, vector<PII>, greater<PII>> que;
  fill(d, d+n, INF);
  REP(i, k) {
    d[s[i]] = 0;
    que.push(PII{0, s[i]});
  }

  while(que.size()) {
    PII p = que.top(); que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    for(edge e: g[v]) {
      if(d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(PII{d[e.to], e.to});
      }
    }
  }
}

int a[100010], b[100010], c[100010];
signed main(void)
{
  cin >> n >> m >> k;
  REP(i, m) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--, b[i]--;
    g[a[i]].PB({b[i], c[i]});
    g[b[i]].PB({a[i], c[i]});
  }
  REP(i, k) cin >> s[i], s[i]--;

  dijkstra();
  // REP(i, n) cout << d[i] << " "; cout << endl;

  int ret = 0;
  REP(i, m) chmax(ret, (d[a[i]]+d[b[i]]+c[i])/2+!!((d[a[i]]+d[b[i]]+c[i])%2));
  cout << ret << endl;

  return 0;
}