import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static ArrayList<Edge>[] arr;
static HashMap<Integer, Integer>[] dist;
//static HashMap<Integer, ArrayList<Edge>>[] arr;
static HashMap<Integer, Integer>[] recolor; // Stores the cost to recolor all edges of a certain color at a node
public static void main(String[] args) throws IOException{
BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader file = new BufferedReader(new FileReader("file.in"));
// PrintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("Robot.out")));
StringTokenizer st = new StringTokenizer(file.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
//arr = new HashMap[n];
arr = new ArrayList[n];
recolor = new HashMap[n];
dist = new HashMap[n];
recolor = new HashMap[n];
for (int i=0; i<n; i++){
arr[i] = new ArrayList<>();
recolor[i] = new HashMap<>();
dist[i] = new HashMap<>();
recolor[i] = new HashMap<>();
}
for (int i=0; i<m; i++){
st = new StringTokenizer(file.readLine());
int s = Integer.parseInt(st.nextToken())-1;
int e = Integer.parseInt(st.nextToken())-1;
int color = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
arr[s].add(new Edge(e, color, cost));
arr[e].add(new Edge(s, color, cost));
addEdge(s, e, color, cost);
addEdge(e, s, color, cost);
}
// Do Dijkstra on expanded states. State = current node, the original color of the edge we just walked through,
// (if we recolored it). Total N+M states.
PriorityQueue<State> pq = new PriorityQueue<>();
pq.add(new State(0, -1, 0, 0));
while (!pq.isEmpty()){
State curr = pq.poll();
if (dist[curr.node].containsKey(curr.prevColor) && dist[curr.node].get(curr.prevColor) != curr.cost){
continue;
}
addUsed(curr.node, curr.prevColor, curr.cost);
for (Edge e : arr[curr.node]){
// if (curr.prevColor == e.color || curr.prevColor == -1){
if (!recolor[curr.node].containsKey(e.color)){
continue;
}
// Determine to recolor all other edges of the same color, or recolor this 1 edge
// if (recolor[curr.node].get(e.color) - curr.prevEdgeCost - e.cost <= e.cost){
// Recolor everything else
int nc = curr.cost + recolor[curr.node].get(e.color) - e.cost;
if (curr.prevColor == e.color){
nc -= curr.prevEdgeCost;
}
if (addUsed(e.to, -1, nc)){
pq.add(new State(e.to, -1, nc, e.cost));
}
// }else if (recolor[curr.node].get(e.color) - curr.prevEdgeCost - e.cost >= e.cost){
if (addUsed(e.to, e.color, curr.cost + e.cost)){
pq.add(new State(e.to, e.color, curr.cost + e.cost, e.cost));
}
// }
// }
}
// if (curr.prevColor != -1){
// // Loop through the edges with color = prevColor
// for (Edge e : arr[curr.node].get(curr.prevColor)){
// if (recolor[curr.node].get(curr.prevColor) - curr.prevEdgeCost >;
// if (dist[e.to].containsKey(e.color) && dist[e.to].get(e.color) <= nc + curr.cost){
// }
// }
// }else{
// for (int color : arr[curr.node].keySet()){
// for (Edge e : arr[curr.node].get(color)){
// }
// }
// }
}
int ans = Integer.MAX_VALUE;
for (int c : dist[n-1].keySet()){
ans = Math.min(dist[n-1].get(c), ans);
}
if (ans == Integer.MAX_VALUE) ans = -1;
System.out.println(ans);
}
public static void addEdge(int ind, int to, int color, int cost){
if (!recolor[ind].containsKey(color)){
// arr[ind].put(color, new ArrayList<>());
recolor[ind].put(color, 0);
}
// arr[ind].get(color).add(new Edge(to, color, cost));
recolor[ind].put(color, recolor[ind].get(color) + cost);
}
public static boolean addUsed(int ind, int prevColor, int newDist){ // Return true if element added, or false if not added
if (!dist[ind].containsKey(prevColor) || dist[ind].get(prevColor) > newDist){
dist[ind].put(prevColor, newDist);
return true;
}
return false;
}
static class State implements Comparable<State>{
int node, prevColor, cost, prevEdgeCost;
public State(int node, int prevColor, int cost, int prevEdgeCost){
this.node = node;
this.prevColor = prevColor;
this.cost = cost;
this.prevEdgeCost = prevEdgeCost;
}
public int compareTo(State o){
return Integer.compare(this.cost, o.cost);
}
}
static class Edge{
int to, color, cost;
public Edge(int to, int color, int cost){
this.to = to;
this.color = color;
this.cost = cost;
}
}
}
Compilation message
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
8588 KB |
Output is correct |
| 2 |
Correct |
65 ms |
8396 KB |
Output is correct |
| 3 |
Correct |
62 ms |
8124 KB |
Output is correct |
| 4 |
Correct |
74 ms |
8344 KB |
Output is correct |
| 5 |
Correct |
82 ms |
8460 KB |
Output is correct |
| 6 |
Incorrect |
63 ms |
8284 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1084 ms |
55232 KB |
Output is correct |
| 2 |
Correct |
725 ms |
35752 KB |
Output is correct |
| 3 |
Correct |
1104 ms |
51192 KB |
Output is correct |
| 4 |
Correct |
837 ms |
42360 KB |
Output is correct |
| 5 |
Execution timed out |
3076 ms |
155460 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
8588 KB |
Output is correct |
| 2 |
Correct |
65 ms |
8396 KB |
Output is correct |
| 3 |
Correct |
62 ms |
8124 KB |
Output is correct |
| 4 |
Correct |
74 ms |
8344 KB |
Output is correct |
| 5 |
Correct |
82 ms |
8460 KB |
Output is correct |
| 6 |
Incorrect |
63 ms |
8284 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
