# Silver Cow Party (POJ 3268)

This is also a problem that demands you caculate distance between every pair of vertices. Instead of simply apply Floyd algorithm, we have to run Dijkstra algorithm N times. That is because the time complexity of Floyd algorithm will be where N is the number of vertices, but if using a priority queue, a single round of Dijkstra algorithm cost so the total time cost is proportional to which is a little faster than Floyd and can pass the tests without time out.

import java.io.*;
import java.util.*;

class Edge {
int u;
int v;
int cost;

public Edge(int u, int v, int cost) {
this.u = u;
this.v = v;
this.cost = cost;
}
}

class Distance implements Comparable<Distance> {
int u;
int d;

public Distance(int u, int d) {
this.u = u;
this.d = d;
}

public int compareTo(Distance another) {
return this.d - another.d;
}
}

public class SilverCowParty {
private static int INF = Integer.MAX_VALUE;

private static int[] getDist(int N, int s, List<List<Edge>> graph) {
int[] dist = new int[N];
Arrays.fill(dist, INF);
dist[s] = 0;

PriorityQueue<Distance> que = new PriorityQueue<Distance>();
que.offer(new Distance(s, 0));

while (!que.isEmpty()) {
Distance p = que.poll();
if (dist[p.u] < p.d) continue;

for (Edge e : graph.get(p.u)) {
if (dist[e.v] > p.d + e.cost) {
dist[e.v] = p.d + e.cost;
que.offer(new Distance(e.v, dist[e.v]));
}
}
}

return dist;
}

public static void main(String[] args) throws IOException {

int N = Integer.parseInt(str[0]), M = Integer.parseInt(str[1]), X = Integer.parseInt(str[2]) - 1;

ArrayList<List<Edge>> graph = new ArrayList<List<Edge>>(N);
for (int i = 0; i < N; i++) graph.add(new ArrayList<Edge>());

for (int i = 0; i < M; i++) {
int a = Integer.parseInt(str[0]) - 1, b = Integer.parseInt(str[1]) - 1, cost = Integer.parseInt(str[2]);
}

int[] xdist = getDist(N, X, graph);
int max = 0;

for (int i = 0; i < N; i++) {
if (i == X) continue;

int[] idist = getDist(N, i, graph);
max = Math.max(max, idist[X] + xdist[i]);
}

System.out.println(max);
}
}