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