AOJ-2249 : Road Construction
問題概要
ノード数V(<10000)、辺数E(<20000)の重み付き無向グラフが与えられる。0を根としたshortest path treeのうちコスト最小のものを求める問題。
解法
Dijkstraした後距離の近い順にソートして確定させていく。
acceptされたコード
計算量O(E*log V)。
#include <cstdio> #include <vector> #include <algorithm> #include <queue> using namespace std; const int MAX_N = 10000; const int INF = 1<<29; struct edge{ int tar, dist, cost; }; int N, M; vector<edge> graph[MAX_N]; int dist[MAX_N], ids[MAX_N]; bool init(){ scanf("%d%d", &N, &M); for(int i=0; i<N; i++){ graph[i].clear(); } for(int i=0; i<M; i++){ int u, v, d, c; scanf("%d%d%d%d", &u, &v, &d, &c); u--; v--; graph[u].push_back((edge){v, d, c}); graph[v].push_back((edge){u, d, c}); } return N > 0; } bool cmp(int i, int j){ return dist[i] < dist[j]; } struct state{ int cur, dist; }; bool operator>(const state& lhs, const state& rhs){ return lhs.dist > rhs.dist; } int solve(){ //dijkstra fill(dist, dist + N, INF); priority_queue<state, vector<state>, greater<state> > que; dist[0] = 0; que.push((state){0, 0}); for(;!que.empty();){ const int v = que.top().cur, d = que.top().dist; que.pop(); if(dist[v] < d){ continue; } for(int i=0; i<(int)graph[v].size(); i++){ const int u = graph[v][i].tar, nd = d + graph[v][i].dist; if(dist[u] > nd){ dist[u] = nd; que.push((state){u, nd}); } } } //solve for(int i=0; i<N; i++){ ids[i] = i; } sort(ids, ids+N, cmp); int ans = 0; for(int i=1; i<N; i++){ int mini = INF; for(int j=0; j<(int)graph[i].size(); j++){ const int u = graph[i][j].tar, d = graph[i][j].dist, c = graph[i][j].cost; if(dist[u] + d == dist[i] && c < mini){ mini = c; } } ans += mini; } return ans; } int main(){ for(;init();){ printf("%d\n", solve()); } return 0; }