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