2249-Road Construction

問題（外部リンク）

Road Construction | Aizu Online Judge

実装の概要

条件より首都から各都市への距離が最短である必要があるので単一始点最短路問題として解きます。Nの値が大きい割に辺の数はM<=20000なので優先度付きキューを用いたダイクストラ法であれば十分間に合います。
今回は距離の計算だけでなく費用の計算も行う必要があります。ただ、経路を完全に記録する必要はなく、直前の都市からある都市Aに移動するためのコストを配列に保存させれば十分です。
これは、最低限の道の本数しかなければ首都から出発したときにある都市に入るための道は1本に限定されるからです。
コストの記録はダイクストラ法での距離の更新時に行います。注意すべきところは、普段とは異なりたとえ距離が同じであってもコストが安いなら更新処理を行うということです。

public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true){
			String[] tmpArray = br.readLine().split(" ");
			
			int n = Integer.parseInt(tmpArray[0]);
			int m = Integer.parseInt(tmpArray[1]);
			
			if(n == 0 && m == 0){
				break;
			}
			
		　　@SuppressWarnings("unchecked")
	        　　ArrayList<Edge> edges[] = new ArrayList[n];
	 
	        　for(int i = 0; i < n; i++){
	            if(edges[i] == null){
	                edges[i] = new ArrayList<Edge>();
	            }
	        }
	        
		for(int i = 0; i < m ; i++){
			tmpArray = br.readLine().split(" ");
			int u = Integer.parseInt(tmpArray[0]) - 1;
			int v = Integer.parseInt(tmpArray[1]) - 1;
			int d = Integer.parseInt(tmpArray[2]);
			int c = Integer.parseInt(tmpArray[3]);
				
			//往路復路の生成
			edges[u].add( new Edge(v, d, c));
			edges[v].add( new Edge(u, d, c));
		}
			
			solve(edges, n, 0);
		}

	}

	static void solve(ArrayList<Edge>[] edges,  int n, int x){
        //xからそれぞれのfarmへの帰り道の最短距離
	int preCost[] = new int[n];
        int[] dist = dijkstra(edges, x, n, preCost);
         
        long sum = 0;
        
        for(int i = 0; i < n; i++){
        	if(i == x){
        		continue;
        	}
        	
        	sum += preCost[i];
        }
        
        System.out.println(sum);
 
    }
	
	static final int INF = Integer.MAX_VALUE;

	//ダイクストラ法（cost[]に各点への直前の移動コストを保存）
	static int[] dijkstra(ArrayList<Edge>[] edges, int s, int n, int cost[]){

		PriorityQueue<Distance> que = new PriorityQueue<Distance>();
		int[] dist = new int[n];

		Arrays.fill(dist, INF);
		dist[s] = 0;
		que.add(new Distance(0, s));

		while(!que.isEmpty()){
			Distance tmpDist = que.poll();
			int tmpV = tmpDist.id;

			if(dist[tmpV] < tmpDist.dist){
				continue;
			}

			for(int i = 0; i < edges[tmpV].size() ; i++){
				Edge e = (Edge) edges[tmpV].get(i);
				//今回は距離が同じでもコストが安ければ更新
				if((dist[e.to] == dist[tmpV] + e.dist && cost[e.to] > e.cost) || (dist[e.to] > dist[tmpV] + e.dist)){
					dist[e.to] = dist[tmpV] + e.dist;
					que.add(new Distance(dist[e.to], e.to));
					
					//cost情報の記憶
					cost[e.to] = e.cost;
					
				}
			}
		}

		return dist;
	}

}

class Distance implements Comparable<Distance>{
	int dist;
	int id;

	Distance(int dist, int id){
		this.dist = dist;
		this.id = id;
	}

	@Override
	public int compareTo(Distance d) {
		return this.dist - d.dist;
	}
}

class Edge {
	int to;
	int dist;
	int cost;

	Edge(int to, int dist, int cost){
		this.to = to;
		this.dist = dist;
		this.cost = cost;
	}
}