Submission #502463

#	Time	Username	Problem	Language	Result	Execution time	Memory
502463		nicolexxuu	Robot (JOI21_ho_t4)	Java	0 / 100	646 ms	39284 KiB

Main

// Robot - JOI '21

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));
		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];
		long[] dist = new long[N+1];
		HashMap<Integer, Long>[] psum = 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<>();
		}
		
		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<>();
		boolean[] mark = new boolean[N+1];
		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;
			long p = curr.e.p; // >0 if prev node (same color as curr) was recolored
//			if(mark[id]) continue; // will give incorrect answer ? disregards different e.p
			if(dist[id] != total) continue;
//			System.out.println("id: " + id + " total: " + total);
			
			for(Edge e : adj[id]) {
//				System.out.println("edge to " + e.to);
				// Case 1: recolor e's same-colored neighbors
				// if the prev node was already recolored, don't double count it
				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)));
//					System.out.println("adding");
				}
				
				// Case 2: recolor e
				recolor = e.p;
				if(total + recolor < dist[e.to]) { // <= ? 
					dist[e.to] = total + recolor; 
					if(e.c == c) toVisit.add(new QueueEntry(dist[e.to], e));
					toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
//					System.out.println("adding");
				}
				
			}
		}
		
		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;
		long p;
		Edge(int to, int c, long 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