import java.util.*;
class Main {
public static void main (String[]args) {
Scanner scan = new Scanner (System.in);
int nodeNumber = scan.nextInt();
int edgeNumber = scan.nextInt();
int startNode = scan.nextInt() - 1;
int endNode = scan.nextInt() - 1;
int bookStoreOne = scan.nextInt() - 1;
int bookStoreTwo = scan.nextInt() - 1;
Hashtable <Integer, ArrayList<Pair>> weightedGraph = new Hashtable <Integer, ArrayList<Pair>>();
for (int i = 0; i < nodeNumber; i++) {
weightedGraph.put(i, new ArrayList<Pair>());
}
for (int i = 0; i < edgeNumber; i++) {
int firstNode = scan.nextInt() - 1;
int secondNode = scan.nextInt() - 1;
long edgeCost = scan.nextLong();
ArrayList<Pair> temp = weightedGraph.get(firstNode);
temp.add(new Pair(secondNode, edgeCost));
weightedGraph.put(firstNode, temp);
ArrayList<Pair> tempTwo = weightedGraph.get(secondNode);
tempTwo.add(new Pair(firstNode, edgeCost));
weightedGraph.put(secondNode, tempTwo);
}
long [] storeOneDistances = dijkstra(bookStoreOne, weightedGraph);
long [] storeTwoDistances = dijkstra(bookStoreTwo, weightedGraph);
long [] startDistances = dijkstra(startNode, weightedGraph);
long initialValue = storeOneDistances[bookStoreTwo];
/*
*
*/
long [][][] dp = new long [nodeNumber][2][2];
for (int i = 0; i < nodeNumber; i++) {
for (int j = 0; j < 2; j++) {
Arrays.fill(dp[i][j], Long.MAX_VALUE);
}
}
dp[startNode][0][0] = 0;
PriorityQueue <pqQuad> pq = new PriorityQueue <pqQuad>();
pq.add(new pqQuad(startNode, 0, 0, 0));
while (pq.isEmpty() == false) {
pqQuad curQuad = pq.poll();
int curNode = curQuad.node;
int firstStage = curQuad.firstStage;
int secondStage = curQuad.secondStage;
long distance = curQuad.distanceFromStart;
if (distance != dp[curNode][firstStage][secondStage]) {
continue;
}
ArrayList<Pair> neighbors = weightedGraph.get(curNode);
for (int i = 0; i < neighbors.size(); i++) {
int neighborNode = neighbors.get(i).secondNode;
long edgeCost = neighbors.get(i).edgeCost;
// Connect to the start node
if (dp[curNode][1][secondStage] > dp[curNode][firstStage][secondStage] + storeOneDistances[curNode]) {
dp[curNode][1][secondStage] = dp[curNode][firstStage][secondStage] + storeOneDistances[curNode];
pq.add(new pqQuad(curNode, 1, secondStage, dp[curNode][1][secondStage]));
}
// Connect to the end node
if (dp[curNode][firstStage][1] > dp[curNode][firstStage][secondStage] + storeTwoDistances[curNode]) {
dp[curNode][firstStage][1] = dp[curNode][firstStage][secondStage] + storeTwoDistances[curNode];
pq.add(new pqQuad(curNode, firstStage, 1, dp[curNode][firstStage][1]));
}
// Move to the neighbor node
if (dp[neighborNode][firstStage][secondStage] > dp[curNode][firstStage][secondStage] && startDistances[curNode] + edgeCost == startDistances[neighborNode]) {
dp[neighborNode][firstStage][secondStage] = dp[curNode][firstStage][secondStage];
pq.add(new pqQuad(neighborNode, firstStage, secondStage, dp[neighborNode][firstStage][secondStage]));
}
}
}
System.out.println(Math.min(storeOneDistances[bookStoreTwo], dp[endNode][1][1]));
}
private static class pqQuad implements Comparable<pqQuad> {
int node;
int firstStage;
int secondStage;
long distanceFromStart;
public pqQuad (int node, int firstStage, int secondStage, long distanceFromStart) {
this.node = node;
this.firstStage = firstStage;
this.secondStage = secondStage;
this.distanceFromStart = distanceFromStart;
}
public int compareTo (pqQuad p) {
if (distanceFromStart < p.distanceFromStart) {
return (-1);
}
return (1);
}
}
public static long[] dijkstra (int startNode, Hashtable <Integer, ArrayList<Pair>> weightedGraph) {
int nodeNumber = weightedGraph.size();
long [] distances = new long [nodeNumber];
Arrays.fill(distances, Long.MAX_VALUE);
distances[startNode] = 0;
PriorityQueue <pqPair> pq = new PriorityQueue <pqPair>();
pq.add(new pqPair(startNode, 0));
while (pq.isEmpty() == false) {
pqPair curPair = pq.poll();
int curNode = curPair.node;
ArrayList<Pair> temp = weightedGraph.get(curNode);
for (int i = 0; i < temp.size(); i++) {
int neighborNode = temp.get(i).secondNode;
long edgeCost = temp.get(i).edgeCost;
if (distances[neighborNode] > distances[curNode] + edgeCost) {
distances[neighborNode] = distances[curNode] + edgeCost;
pq.add(new pqPair(neighborNode, distances[neighborNode]));
}
}
}
return (distances);
}
private static class pqPair implements Comparable<pqPair> {
int node;
long distanceFromStart;
public pqPair (int node, long distanceFromStart) {
this.node = node;
this.distanceFromStart = distanceFromStart;
}
public int compareTo (pqPair p) {
if (distanceFromStart < p.distanceFromStart) {
return (-1);
}
return (1);
}
}
private static class Pair {
int secondNode;
long edgeCost;
public Pair (int secondNode, long edgeCost) {
this.secondNode = secondNode;
this.edgeCost = edgeCost;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
133 ms |
12808 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
11988 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
151 ms |
12028 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
133 ms |
12808 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
