3259-Wormholes

問題（外部リンク）

3259 -- Wormholes

実装の概要

今回の問題ではそれぞれのfieldを行き来するのにpathとwormholeを使うことができ、後者では時間を遡ることができます。
つまり、wormholeの移動コストをマイナスとして扱い、負の閉路（移動距離がマイナスとなり、始点と終点が同じであるルート）が存在するかによって答えが決まります。
問題となるのは使用するアルゴリズムです。ワーシャルフロイド法はソースが簡潔かつ辺の長さが負でも使用できますが、となり間に合いません。
そこで、ベルマンフォード法をアレンジして負の閉路を見つけることに特化したアルゴリズム（蟻本に掲載されているものを参考にしました）を使用することででYESかNOかを判定できるようになります。
似たような話でより高速なダイクストラ法もありますが、こちらは負のコストがあると使えないので今回は不採用となります。

public class Main {
	static final int INF = 99999999;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int f = Integer.parseInt(br.readLine());

		for(int u = 0; u < f; u++){
			String[] tmpArray = br.readLine().split(" ");

			int n = Integer.parseInt(tmpArray[0]);
			int m = Integer.parseInt(tmpArray[1]);
			int w = Integer.parseInt(tmpArray[2]);
			
			Edge[] edges = new Edge[m*2 + w];

			for(int i = 0; i < m; i++){
				tmpArray = br.readLine().split(" ");

				int s = Integer.parseInt(tmpArray[0]) - 1;
				int e = Integer.parseInt(tmpArray[1]) - 1;
				int d = Integer.parseInt(tmpArray[2]);

				//pathは往路も復路もあるので注意
				edges[i*2] = new Edge(s, e, d);
				edges[i*2+1] = new Edge(e, s, d);

			}

			for(int i = 0; i < w; i++){
				tmpArray = br.readLine().split(" ");

				int s = Integer.parseInt(tmpArray[0]) - 1;
				int e = Integer.parseInt(tmpArray[1]) - 1;
				//wormholeなので距離は負
				int d = -1*Integer.parseInt(tmpArray[2]);

				//wormholeは片道だけで良い
				edges[i + m*2] = new Edge(s, e, d);
			}
			
			if(findNegativeLoop(n, edges)){
				System.out.println("YES");
			}
			else {
				System.out.println("NO");
			}
		}
	}

	//負の閉路が存在するかを調べる
	static boolean findNegativeLoop(int n, Edge[] edges){
		int dist[] = new int[n];
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < edges.length; j++){
				Edge tmpEdge = edges[j];
				
				if(dist[tmpEdge.to] > dist[tmpEdge.from] + tmpEdge.cost){
					dist[tmpEdge.to] = dist[tmpEdge.from] + tmpEdge.cost;
					
					if(i == n - 1){
						return true;
					}
				}
			}
		}
		return false;
	}

}

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