Code: Select all
public class HighestPaidToll_12047 {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int test = in.nextInt();
int n, m, s, t, p, i, a, b, c;
List<Edge> graph[] = new List[10000];
List<Edge> rGraph[] = new List[10000];
Vertex vertex[] = new Vertex[10000];
Vertex rVertex[] = new Vertex[10000];
Edges edges[] = new Edges[100000];
for(i=0;i<10000;i++) {
graph[i] = new ArrayList<Edge>(1000);
rGraph[i] = new ArrayList<Edge>(1000);
vertex[i] = new Vertex(i);
rVertex[i] = new Vertex(i);
}
while (test-- > 0) {
n = in.nextInt();
m = in.nextInt();
s = in.nextInt() - 1;
t = in.nextInt() - 1;
p = in.nextInt();
for(i=0;i<n;i++) {
graph[i].clear();
rGraph[i].clear();
vertex[i].key = Integer.MAX_VALUE;
rVertex[i].key = Integer.MAX_VALUE;
vertex[i].visited = false;
rVertex[i].visited = false;
}
for(i=0;i<m;i++) {
a = in.nextInt() - 1;
b = in.nextInt() - 1;
c = in.nextInt();
graph[a].add(new Edge(vertex[b], c));
rGraph[b].add(new Edge(rVertex[a], c));
edges[i] = new Edges(a, b, c);
}
Dijkstra(graph, vertex, s);
Dijkstra(rGraph, rVertex, t);
int max = -1, u, v;
for(i=0;i<m;i++) {
if(edges[i].c > max) {
u = edges[i].u;
v = edges[i].v;
if(vertex[u].key != Integer.MAX_VALUE && rVertex[v].key != Integer.MAX_VALUE) {
if(vertex[u].key + rVertex[v].key + edges[i].c <= p)
max = edges[i].c;
}
}
}
out.printLine(max);
}
}
class Edges {
int u, v;
int c;
public Edges(int u, int v, int c) {
this.u = u;
this.v = v;
this.c = c;
}
}
public void Dijkstra(List<Edge> graph[], Vertex a[], int source) {
a[source].key = 0;
PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();
pq.add(a[source]);
while (!pq.isEmpty()) {
Vertex u = pq.poll();
if(!u.visited) {
u.visited = true;
for(Edge e : graph[u.index]) {
Vertex v = e.dest;
if(v.key > u.key + e.cost) {
//v.parent = u.index;
v.key = u.key + e.cost;
pq.add(v);
}
}
}
}
}
class Vertex implements Comparable<Vertex> {
public boolean visited;
public int parent, key, index, indexInHeap;
public List<Edge> edges;
public Vertex(int index) {
this.index = index;
visited = false;
parent = -1;
key = Integer.MAX_VALUE;
edges = new ArrayList<Edge>();
indexInHeap = index;
}
public int compareTo(Vertex o) {
return this.key - o.key;
}
}
class Edge {
public Vertex dest;
public int cost;
public Edge(Vertex dest, int cost) {
this.dest = dest;
this.cost = cost;
}
}
}