import java.util.*;
import java.io.*;
public class commuter_pass {
static long[] distance;
static boolean[] visited;
static ArrayList<Edge>[] edges;
static int n;
static ArrayList<Integer> path;
public static void main(String[] args) throws IOException{
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader input = new BufferedReader(new FileReader("cp.in"));
// PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("cp.out")));
StringTokenizer st = new StringTokenizer(input.readLine());
n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
st = new StringTokenizer(input.readLine());
int s = Integer.parseInt(st.nextToken()) - 1;
int t = Integer.parseInt(st.nextToken()) - 1;
st = new StringTokenizer(input.readLine());
int u = Integer.parseInt(st.nextToken()) - 1;
int v = Integer.parseInt(st.nextToken()) - 1;
distance = new long[n];
visited = new boolean[n];
edges = new ArrayList[n];
for (int i = 0; i < n; i++)
{
edges[i] = new ArrayList<Edge>();
}
for (int i = 0; i < m; i++)
{
st = new StringTokenizer(input.readLine());
int one = Integer.parseInt(st.nextToken()) - 1;
int two = Integer.parseInt(st.nextToken()) - 1;
int weight = Integer.parseInt(st.nextToken());
Edge edge = new Edge(weight, one, two);
edges[one].add(edge);
edges[two].add(edge);
}
getShortestPath(s, t);
// System.out.println(distance[t]);
getPath(s, t);
// printPath();
getShortestPath(u, v);
System.out.println(distance[v]);
}
static void getShortestPath(int start, int end) {
Arrays.fill(distance, Long.MAX_VALUE);
Arrays.fill(visited, false);
int current = start;
distance[current] = 0;
while (!visited[end]) {
visited[current] = true;
for (Edge edge : edges[current])
{
int other = edge.getOther(current);
if (distance[other] > (distance[current] + edge.weight))
{
distance[other] = distance[current] + edge.weight;
}
}
current = getNext();
}
}
static int getNext() {
long value = Long.MAX_VALUE;
int index = -1;
for (int i = 0; i < n; i++)
{
if (!visited[i] && distance[i] < value)
{
value = distance[i];
index = i;
}
}
return index;
}
static void getPath(int start, int end) {
path = new ArrayList<>();
long pw = distance[end];
int current = end;
path.add(end+1);
while (pw > 0)
{
for (Edge edge : edges[current])
{
int other = edge.getOther(current);
if (edge.weight == (distance[current] - distance[other]))
{
pw = pw - edge.weight;
edge.weight = 0;
current = other;
path.add(current+1);
break;
}
}
}
}
static void printPath() {
for (int i : path) {
System.out.print(i + " - ");
}
System.out.println();
}
static class Edge {
int weight;
int one;
int two;
public Edge (int weight, int one, int two) {
this.weight = weight;
this.one = one;
this.two = two;
}
public int getOther (int current) {
return current == this.one ? this.two : this.one;
}
}
}
Compilation message
Note: commuter_pass.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2098 ms |
33960 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2063 ms |
34016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
420 ms |
16188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2098 ms |
33960 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
