AOJ 0562 JOI国の買い物事情
JOI本選まで一週間を切っています
動的計画法の問題を安定して解けるようになりたい
解法
dijkstra法使う
#include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; const int INF = 1 << 29; const int MAX_V = 3000, MAX_E = 100000; typedef pair<int, int> P; typedef pair<int, int> EDGE; vector<EDGE> G[MAX_E]; vector<int> shop; int V, E, K; int d[MAX_V]; int main(){ scanf("%d %d %d", &V, &E, &K); fill(d, d + V, INF); for(int i = 0; i < E; i++){ int a, b, l; scanf("%d %d %d", &a, &b, &l); a--; b--; G[a].push_back(EDGE(l, b)); G[b].push_back(EDGE(l, a)); } priority_queue<P, vector<P>, greater<P> > Q; for(int i = 0; i < K; i++){ int a; scanf("%d", &a); a--; d[a] = 0; Q.push(P(0, a)); } while(!Q.empty()){ P e = Q.top(); Q.pop(); int dist = e.first; int v = e.second; if(d[v] < dist) continue; for(int i = 0; i < G[v].size(); i++){ int u = G[v][i].second; int dd = G[v][i].first; if(dist + dd < d[u]){ d[u] = dist + dd; Q.push(P(d[u], u)); } } } int ans = 0; for(int v = 0; v < V; v++){ for(int j = 0; j < G[v].size(); j++){ int l = G[v][j].first; int u = G[v][j].second; ans = max(ans, (d[v] + d[u] + l + 1) / 2); } } printf("%d\n", ans); return 0; }