import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static HashMap<Integer, ArrayList<Edge>>[] arr;
static HashMap<Integer, Long>[] recolor;
// static long[] dp; // dp[i] = min dist to get to node i
// static HashMap<Integer, Long>[] dp2; // dp2[i][c] = min cost to get to i, given we just recolored an edge of color c
static HashMap<Integer, Long>[][] dist;
static int[] edgeColor, edgeCost;
static PriorityQueue<State> pq;
public static void main(String[] args) throws IOException{
FastIO file = new FastIO();
// 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")));
n = file.nextInt();
m = file.nextInt();
arr = new HashMap[n];
recolor = new HashMap[n];
dist = new HashMap[n][2];
// dp = new long[n];
// dp2 = new HashMap[n];
for (int i=0; i<n; i++){
arr[i] = new HashMap<>();
recolor[i] = new HashMap<>();
// dp2[i] = new HashMap<>();
dist[i][0] = new HashMap<>();
dist[i][1] = new HashMap<>();
}
int[] edgeColor = new int[m];
int[] edgeCost = new int[m];
for (int i=0; i<m; i++){
int s = file.nextInt()-1;
int e = file.nextInt()-1;
int c = file.nextInt();
int p = file.nextInt();
if (!recolor[s].containsKey(c)){
recolor[s].put(c, 0L);
arr[s].put(c, new ArrayList<>());
}
if (!recolor[e].containsKey(c)){
recolor[e].put(c, 0L);
arr[e].put(c, new ArrayList<>());
}
arr[s].get(c).add(new Edge(e, c, p, i));
arr[e].get(c).add(new Edge(s, c, p, i));
recolor[s].put(c, recolor[s].get(c) + p);
recolor[e].put(c, recolor[e].get(c) + p);
edgeColor[i] = c;
edgeCost[i] = p;
}
pq = new PriorityQueue<>();
add(0, -1, 0, 0);
while (!pq.isEmpty()){
State curr = pq.poll();
if (curr.colorLater == 1){
// We recolored the edge we walked through, so only loop through edges of the same color
if (dist[curr.node][1].get(edgeColor[curr.prevEdge]) != curr.cost){
continue;
}
for (Edge e : arr[curr.node].get(edgeColor[curr.prevEdge])){
if (e.id == curr.prevEdge){
continue;
}
long nc = curr.cost + recolor[curr.node].get(e.c) - e.p;
if (!dist[e.to][0].containsKey(-1) || nc < dist[e.to][0].get(-1)){
pq.add(new State(e.to, e.id, 0, nc));
dist[e.to][0].put(-1, nc);
}
}
}else{
if (dist[curr.node][0].get(-1) != curr.cost){
continue;
}
// We didn't recolor the previous edge, so loop through all colors
for (int color : arr[curr.node].keySet()){
for (Edge e : arr[curr.node].get(color)){
if (e.id == curr.prevEdge){
continue;
}
// Recolor edge e, but we don't plan to go through another edge of color e.c (explore all possibilities)
long case1 = curr.cost + e.p;
if (!dist[e.to][0].containsKey(-1) || case1 < dist[e.to][0].get(-1)){
dist[e.to][0].put(-1, case1);
pq.add(new State(e.to, e.id, 0,case1));
}
// Recolor all other edges
long case2 = curr.cost + recolor[curr.node].get(e.c) - e.p;
if (!dist[e.to][0].containsKey(-1) || case2 < dist[e.to][0].get(-1)){
dist[e.to][0].put(-1, case2);
pq.add(new State(e.to, e.id, 0, case2));
}
// Recolor edge e, and we will go through another edge of color e.c. We will recolor edge e when we get
// to e.to, by recoloring all other edges of color e.c (since we will go through another edge of e.c).
long case3 = curr.cost;
if (!dist[e.to][1].containsKey(e.c) || case3 < dist[e.to][1].get(e.c)){
dist[e.to][1].put(e.c, case3);
pq.add(new State(e.to, e.id, 1, case3));
}
}
}
}
}
long ans = Long.MAX_VALUE;
for (long d : dist[n-1][0].values()){
ans = Math.min(ans, d);
}
if (ans == Long.MAX_VALUE) ans = -1;
file.println(ans);
file.close();
}
public static void add(int node, int prevEdge, int colorLater, long cost){
if (!dist[node][colorLater].containsKey(prevEdge) || cost < dist[node][colorLater].get(prevEdge)){
dist[node][colorLater].put(prevEdge, cost);
pq.add(new State(node, prevEdge, colorLater, cost));
}
}
static class Edge{
int to, c, p, id;
public Edge(int to, int c, int p, int id){
this.to = to;
this.c = c;
this.p = p;
this.id = id;
}
}
static class State implements Comparable<State>{
int node, prevEdge, colorLater;
long cost;
public State(int node, int prevEdge, int colorLater, long cost){
this.node = node;
this.prevEdge = prevEdge;
this.colorLater = colorLater;
this.cost = cost;
}
public int compareTo(State o){
return Long.compare(this.cost, o.cost);
}
}
static class FastIO extends PrintWriter {
private InputStream stream;
private byte[] buf = new byte[1<<16];
private int curChar, numChars;
// standard input
public FastIO() { this(System.in,System.out); }
public FastIO(InputStream i, OutputStream o) {
super(o);
stream = i;
}
// file input
public FastIO(String i, String o) throws IOException {
super(new FileWriter(o));
stream = new FileInputStream(i);
}
// throws InputMismatchException() if previously detected end of file
private int nextByte() {
if (numChars == -1) throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars == -1) return -1; // end of file
}
return buf[curChar++];
}
// to read in entire lines, replace c <= ' '
// with a function that checks whether c is a line break
public String next() {
int c; do { c = nextByte(); } while (c <= ' ');
StringBuilder res = new StringBuilder();
do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
return res.toString();
}
public int nextInt() { // nextLong() would be implemented similarly
int c; do { c = nextByte(); } while (c <= ' ');
int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = 10*res+c-'0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public double nextDouble() { return Double.parseDouble(next()); }
}
}
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 |
65 ms |
8292 KB |
Output is correct |
2 |
Correct |
68 ms |
8368 KB |
Output is correct |
3 |
Correct |
59 ms |
8488 KB |
Output is correct |
4 |
Correct |
62 ms |
8496 KB |
Output is correct |
5 |
Correct |
63 ms |
8512 KB |
Output is correct |
6 |
Correct |
59 ms |
8216 KB |
Output is correct |
7 |
Correct |
102 ms |
9236 KB |
Output is correct |
8 |
Correct |
81 ms |
8832 KB |
Output is correct |
9 |
Correct |
173 ms |
12688 KB |
Output is correct |
10 |
Correct |
176 ms |
12868 KB |
Output is correct |
11 |
Correct |
138 ms |
11676 KB |
Output is correct |
12 |
Correct |
140 ms |
11740 KB |
Output is correct |
13 |
Correct |
162 ms |
12348 KB |
Output is correct |
14 |
Correct |
156 ms |
12384 KB |
Output is correct |
15 |
Correct |
135 ms |
11520 KB |
Output is correct |
16 |
Correct |
159 ms |
11952 KB |
Output is correct |
17 |
Correct |
142 ms |
11856 KB |
Output is correct |
18 |
Correct |
87 ms |
9100 KB |
Output is correct |
19 |
Correct |
123 ms |
9668 KB |
Output is correct |
20 |
Correct |
130 ms |
11696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1042 ms |
82396 KB |
Output is correct |
2 |
Correct |
778 ms |
54504 KB |
Output is correct |
3 |
Correct |
1259 ms |
73056 KB |
Output is correct |
4 |
Correct |
843 ms |
64344 KB |
Output is correct |
5 |
Correct |
2920 ms |
210284 KB |
Output is correct |
6 |
Execution timed out |
3099 ms |
189368 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
8292 KB |
Output is correct |
2 |
Correct |
68 ms |
8368 KB |
Output is correct |
3 |
Correct |
59 ms |
8488 KB |
Output is correct |
4 |
Correct |
62 ms |
8496 KB |
Output is correct |
5 |
Correct |
63 ms |
8512 KB |
Output is correct |
6 |
Correct |
59 ms |
8216 KB |
Output is correct |
7 |
Correct |
102 ms |
9236 KB |
Output is correct |
8 |
Correct |
81 ms |
8832 KB |
Output is correct |
9 |
Correct |
173 ms |
12688 KB |
Output is correct |
10 |
Correct |
176 ms |
12868 KB |
Output is correct |
11 |
Correct |
138 ms |
11676 KB |
Output is correct |
12 |
Correct |
140 ms |
11740 KB |
Output is correct |
13 |
Correct |
162 ms |
12348 KB |
Output is correct |
14 |
Correct |
156 ms |
12384 KB |
Output is correct |
15 |
Correct |
135 ms |
11520 KB |
Output is correct |
16 |
Correct |
159 ms |
11952 KB |
Output is correct |
17 |
Correct |
142 ms |
11856 KB |
Output is correct |
18 |
Correct |
87 ms |
9100 KB |
Output is correct |
19 |
Correct |
123 ms |
9668 KB |
Output is correct |
20 |
Correct |
130 ms |
11696 KB |
Output is correct |
21 |
Correct |
1042 ms |
82396 KB |
Output is correct |
22 |
Correct |
778 ms |
54504 KB |
Output is correct |
23 |
Correct |
1259 ms |
73056 KB |
Output is correct |
24 |
Correct |
843 ms |
64344 KB |
Output is correct |
25 |
Correct |
2920 ms |
210284 KB |
Output is correct |
26 |
Execution timed out |
3099 ms |
189368 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |