3269-Silver Cow Party

問題（外部リンク）

3268 -- Silver Cow Party

実装の概要

（2/20 下部に追記あり）
パーティー会場xまでの往復距離の最大値を求めたいので、それぞれの地点からxまでの最短距離と、xからそれぞれの地点までの最短距離を求める必要があります。
N<=1000なのでアルゴリズム選びに気をつける必要があります。ワーシャルフロイドを使いたいところですが常にとなりおそらく厳しいです（実は試していません）。M<=100000なのでベルマンフォード法を頂点の数だけ繰り返すと更に悪化します。
そこで今回はfarm間の距離が正なのでダイクストラ法を使いました。優先度付きキューを用いた場合、ダイクストラ法1回につき計算量はとなり、これを頂点の数だけ行うととなります。NとMがともに最大の場合はほとんど計算量が変わりませんが、Nが大きい割にMが小さい場合はかなり速くなります。

実装その1

public class Main {
	static final int INF = Integer.MAX_VALUE;

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

		String[] tmpArray = br.readLine().split(" ");

		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);
		//0からスタートにしたいのでわざと1引いておく
		int x = Integer.parseInt(tmpArray[2]) - 1;

		ArrayList<Edge> edges[] = new ArrayList[m];

		for(int i = 0; i < m; i++){
			tmpArray = br.readLine().split(" ");
			int from = Integer.parseInt(tmpArray[0]) - 1;
			int to = Integer.parseInt(tmpArray[1]) - 1;
			int cost = Integer.parseInt(tmpArray[2]);

			if(edges[from] == null){
				edges[from] = new ArrayList<Edge>();
			}
			edges[from].add( new Edge(to, cost));
		}

		System.out.println(solve(edges, n, x));
	}

	static int solve(ArrayList[] edges, int n, int x){
		//xからそれぞれのfarmへの帰り道の最短距離
		int[] distBack = dijkstra(edges, x, n);

		int maxDist = 0;
		for(int i = 0; i < n; i++){
			if(i == x){
				continue;
			}

			//iからそれぞれのfarmへの最短距離
			int[] distForward = dijkstra(edges, i, n);

			//往路+復路の最大値を更新する
			maxDist = Math.max(maxDist, distForward[x] + distBack[i]);
		}

		return maxDist;
	}

	//ダイクストラ法
	static int[] dijkstra(ArrayList[] edges, int s, int n){
		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.cost){
					dist[e.to] = dist[tmpV] + e.cost;
					que.add(new Distance(dist[e.to], e.to));
				}
			}
		}

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

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

（追記）
より直感的かつ高速な方法に気づいたので更新します。
往路の計算は事前に入力と逆向きの辺のリストを作っておくことで復路と同じ要領で計算が可能になります。これにより計算量をまで落とすことができます。

実装その2

（各クラスの定義およびダイクストラ法の計算はその1と同じです）

public class Main {
	static final int INF = Integer.MAX_VALUE;

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

		String[] tmpArray = br.readLine().split(" ");

		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);
		//0からスタートにしたいのでわざと1引いておく
		int x = Integer.parseInt(tmpArray[2]) - 1;

		ArrayList<Edge> edges[] = new ArrayList[m];
		//全ての辺の向きを逆向きにして保存しておく
		ArrayList<Edge> edges2[] = new ArrayList[m];

		for(int i = 0; i < m; i++){
			tmpArray = br.readLine().split(" ");
			int from = Integer.parseInt(tmpArray[0]) - 1;
			int to = Integer.parseInt(tmpArray[1]) - 1;
			int cost = Integer.parseInt(tmpArray[2]);

			//入力のとおりの向き
			if(edges[from] == null){
				edges[from] = new ArrayList<Edge>();
			}
			edges[from].add( new Edge(to, cost));

			//逆向き
			if(edges2[to] == null){
				edges2[to] = new ArrayList<Edge>();
			}
			edges2[to].add( new Edge(from, cost));
		}

		System.out.println(solve(edges, edges2, n, x));
	}

	static int solve(ArrayList[] edges1, ArrayList[] edges2, int n, int x){
		//xからそれぞれのfarmへの帰り道の最短距離
		int[] distBack = dijkstra(edges1, x, n);
		int[] distForward = dijkstra(edges2, x, n);

		int maxDist = 0;
		for(int i = 0; i < n; i++){
			if(i == x){
				continue;
			}

			//往路+復路の最大値を更新する
			maxDist = Math.max(maxDist, distForward[i] + distBack[i]);
		}

		return maxDist;
	}