AOJ1311 Test Case Tweaking - nanikakaのAOJ航海日誌

概要

N個の頂点とM本の有向辺からなるグラフがある。頂点1から頂点Nまでの最短経路のコストがちょうどCになるようにしたい。辺のコストが非負であるという制約のもとで、コストを任意に変えていいとき、コストを変更するべき辺の最小本数を求めよ。なお、以下のことが保証されている。
2 <= N <= 100
1 <= M <= 1000
0 <= C <= 100000
0 <= 辺のコスト <= 10000
与えられる最初のグラフの最短経路のコストはCより大きい
自己ループ辺は存在しない
ある頂点のペアの間にある辺は高々1本

解法

ダイクストラで解きます。
ある辺のコストを変えようと考えたとき、コストを好きなだけ減らせるのでかなりの自由度があるわけですが、常に0としてしまいます。最終的に最短経路のコストがC以下ならば、最短経路のコストをちょうどCになるような辺の減らし方が存在するので、0としてしまっても正しい解が求められます。
ダイクストラは(頂点、辺のコストを変更した回数）の拡張頂点上で行います。
d[i][K]: 辺のコストをK回変更して頂点iに辿りつくときの最小コスト
Kの上限についてですが、N-1だけあれば十分でしょう。1からNに行くために通過する辺の最大本数はN-1本で、これらを全て0にするときが最悪の場合だからです。
ダイクストラを走らせた後は、
d[N][k]がC以下となっているような最小のkが答えとなります。

ソース

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

//Test Case Tweaking
public class AOJ1311 {

	class E{
		int t, c;
		public E(int t, int c) {
			this.t = t;
			this.c = c;
		}
	}
	
	int[][] d;
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		int INF = 1<<29;
		for(;;){
			int n = sc.nextInt(), m = sc.nextInt(), C = sc.nextInt();
			if((n|m|C)==0)break;
			List<E>[] e = new List[n+1];
			for(int i=1;i<=n;i++)e[i]=new ArrayList<E>();
			while(m--!=0){
				int s = sc.nextInt(), t = sc.nextInt(), c = sc.nextInt();
				e[s].add(new E(t, c));
			}
			d = new int[n+1][n+1];
			for(int[]a:d)Arrays.fill(a, INF);
			PriorityQueue<int[]> q = new PriorityQueue<int[]>(n, new Comparator<int[]>() {
				public int compare(int[] o1, int[] o2) {
					return d[o1[0]][o1[1]] - d[o2[0]][o2[1]];
				}
			});
			d[1][0] = 0;
			q.add(new int[]{1, 0});
			while(!q.isEmpty()){
				int[] V = q.poll();
				int v = V[0], K = V[1];
				for(E r:e[v]){
					if(d[v][K]+r.c < d[r.t][K]){
						d[r.t][K] = d[v][K]+r.c; q.add(new int[]{r.t, K});
					}
					if(K+1<=n && d[v][K] < d[r.t][K+1]){
						d[r.t][K+1] = d[v][K]; q.add(new int[]{r.t, K+1});
					}
				}
			}
			for(int k=0;k<=n;k++)if(d[n][k]<=C){
				System.out.println(k); break;
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ1311().run();
	}
}