Submission #519398

#	Time	Username	Problem	Language	Result	Execution time	Memory
519398		nicolexxuu	Robot (JOI21_ho_t4)	Java	0 / 100	3053 ms	125072 KiB

Main

// Robot - JOI '21
// time complexity?

import java.util.*;
import java.io.*;

public class Main  {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		BufferedReader br = new BufferedReader(new FileReader(new File("03-15.txt")));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		ArrayList<Edge>[] adj = new ArrayList[N+1];
		HashMap<Integer, Long>[] psum = new HashMap[N+1];
		long[] dist = new long[N+1];
		HashMap<Integer, Long>[] dist2 = new HashMap[N+1];
		Arrays.fill(dist, Long.MAX_VALUE);
		for(int i = 0; i <= N; i++) {
			adj[i] = new ArrayList<>();
			psum[i] = new HashMap<>();
			dist2[i] = new HashMap<>();
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int p = Integer.parseInt(st.nextToken());
			adj[a].add(new Edge(b, c, p));
			adj[b].add(new Edge(a, c, p));
			add(psum[a], c, p);
			add(psum[b], c, p);
		}
		br.close();
		
		PriorityQueue<QueueEntry> toVisit = new PriorityQueue<>();
		dist[1] = 0;
		toVisit.add(new QueueEntry(0, new Edge(1, 0, 0)));
		while(!toVisit.isEmpty()) {
			QueueEntry curr = toVisit.remove();
			long total = curr.total;
			int id = curr.e.to, c = curr.e.c, p = curr.e.p; 
			
			for(Edge e : adj[id]) {
				if(p > 0) { // special case - we already flipped prev edge 
					if(c != e.c || 
							total != dist2[id].get(c)) continue;
					long recolor = psum[id].get(e.c) - e.p - p;
					if(total + recolor < dist[e.to]) {
						dist[e.to] = total + recolor;
						toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
					}
				} else {
					if(total != dist[id]) continue;
					// Case 1: recolor e's same-colored neighbors
					long recolor = psum[id].get(e.c) - e.p;
					if(total + recolor < dist[e.to]) {
						dist[e.to] = total + recolor; 
						toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
					}
					
					// Case 2: only recolor e
					recolor = e.p;
					if(total + recolor < dist[e.to]) {
						dist[e.to] = total + recolor; 
						toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
					}
					
					// Case 3: recolor curr and future edge
					if(!dist2[e.to].containsKey(e.c) || total+recolor < dist2[e.to].get(e.c)) {
						add(dist2[e.to], e.c, total+recolor);
						toVisit.add(new QueueEntry(dist2[e.to].get(e.c), e));
					}
				}
			}
		}
		
		System.out.println(dist[N] == Long.MAX_VALUE ? -1 : dist[N]);
	}
	
	public static void add(HashMap<Integer, Long> map, int c, long p) {
		if(!map.containsKey(c)) map.put(c, p);
		else map.replace(c, map.get(c) + p);
	}
	
	public static class Edge {
		int to, c, p;
		Edge(int to, int c, int p) {
			this.to = to;
			this.c = c;
			this.p = p;
		}
	}
	
	public static class QueueEntry implements Comparable<QueueEntry> {
		long total;
		Edge e;
		
		QueueEntry(long total, Edge e) {
			// total = cumulative price, e.p = price of last visited edge
			this.total = total;
			this.e = e;
		}
		
		public int compareTo(QueueEntry other) {
			return Long.compare(total, other.total);
		}
	}
}

Compilation message (stderr)

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42