Submission #519385

#	Time	Username	Problem	Language	Result	Execution time	Memory
519385		nicolexxuu	Robot (JOI21_ho_t4)	Java	34 / 100	3068 ms	93164 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("01-09.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();
		// continue modeling solution
		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; 
//			System.out.println("curr.e: " + curr.e);
			
			for(Edge e : adj[id]) {
//				System.out.println("edge to: " + e.to);
				if(p > 0) { // special case - we already flipped prev edge ?????
//					System.out.println("id: " + id + " c: " + c);
					if(c != e.c || 
							total != dist2[id].get(c)) continue;
					long recolor = psum[id].get(e.c) - e.p;
					if(total + recolor < dist[e.to]) {
						dist[e.to] = total + recolor;
//						System.out.println("1: " + dist[e.to]);
						toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
					}
				} else {
					if(total != dist[id]) continue;
//					System.out.println("got here");
					// 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; 
//						System.out.println("2: " + dist[e.to]);
						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; 
//						System.out.println("4: " + dist[e.to]);
						toVisit.add(new QueueEntry(dist[e.to], new Edge(e.to, e.c, 0)));
					}
					
					
					// Case 3: recolor curr and e
					recolor = e.p;
					if(!dist2[e.to].containsKey(e.c) || total < dist2[e.to].get(e.c)) {
						add(dist2[e.to], e.c, total);
//						System.out.println("e.to: " + e.to + " e.c: " + e.c + " total: " + total);
//						System.out.println("3: " + dist[e.to]);
						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 String toString() { return "id: " + to + " c: " + c + " 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);
		}
	}
}


/*
4 6
1 4 4 1
3 4 1 1
1 3 4 1
2 4 3 1
2 3 3 1
1 2 4 1

4 4
1 2 3 1
2 3 2 1
3 4 1 1
1 4 2 1
*/

Compilation message (stderr)

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

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