AOJ2249 Road Construction

問題リンク Road Construction

• 概要

N個の街がある。街は1〜Nで番号付けされていて1番の街は首都である。
国王が街同士を結ぶ街道をM本作ろうと計画している。街道は双方向で、街iと街jを結び、その距離はd、建設費用はcである。以下の条件を満たすようにM本の街道のうちからいくつか建設中止して、建設に必要なコストを最小化せよ。
・任意の2つの街について、街道を通って行き来することができる
・首都と街iの最短距離が同じである
また、以下のことが保証されている
街道の両端が同じ街であることはない
街iと街jを結ぶ街道は高々1本である
1 <= N <= 10000
0 <= M <= 20000
1 <= d <= 1000
1 <= c <= 1000

• 解法

首都から各街への最短距離が分からないと話にならないのでダイクストラで求めます。求まったものをdist[]とします。
ここで、街道の各パラメータを{s, t, d, c}とすると
dist[s] + d == dist[t]
を満たしていない街道は取り除いて全く問題ないことが分かります。その街道はもとから最短経路の一部じゃないからです。
同様にある街iに注目して、
dist[s] + d == dist[i]
を満たす街道が複数ある場合、街iへの最短の辿りつき方が複数あることになります。そのような経路が複数あっても無駄なので、最短経路の一部となっている街道の中の最もコストの安いもののみを採用すれば十分です。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

//Road Construction
public class AOJ2249 {

	class E{
		int t, d, c;
		public E(int t, int d, int c) {
			this.t = t;
			this.d = d;
			this.c = c;
		}
	}
	
	int INF = 1<<29;
	int[] dist;
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		dist = new int[10001];
		for(;;){
			int n = sc.nextInt(), m = sc.nextInt();
			if((n|m)==0)break;
			List<E>[] adj = new List[n+1];
			for(int i=0;i<=n;i++)adj[i]=new ArrayList<E>();
			while(m--!=0){
				int s = sc.nextInt(), t = sc.nextInt(), D = sc.nextInt(), C = sc.nextInt();
				adj[s].add(new E(t, D, C)); adj[t].add(new E(s, D, C));
			}
			Arrays.fill(dist, INF);
			dist[1] = 0;
			PriorityQueue<Integer> q = new PriorityQueue<Integer>(n, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					return dist[o1]-dist[o2];
				}
			});
			q.add(1);
			while(!q.isEmpty()){
				int v = q.poll();
				for(E e:adj[v]){
					int w = dist[v]+e.d;
					if(w<dist[e.t]){
						dist[e.t] = w; q.add(e.t);
					}
				}
			}
			int res = 0;
			for(int i=2;i<=n;i++){
				E edge = null;
				for(E e:adj[i]){
					if(dist[e.t]+e.d!=dist[i])continue;
					if(edge==null)edge = e;
					else if(e.c<edge.c)edge = e;
				}
				res+=edge.c;
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2249().run();
	}
}