Submission #617972
Source Code Expand
import java.io.BufferedWriter; import java.io.FileInputStream; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; public class Main { public static void main(String[] args) throws NumberFormatException, IOException {Solve solve = new Solve();solve.solve();} } class Solve{ void dump(int[]a){for(int i=0;i<a.length;i++)System.out.print(a[i]+" ");System.out.println();}; void dump(long[]a){for(int i=0;i<a.length;i++)System.out.print(a[i]+" ");System.out.println();}; void dump(char[]a){for(int i=0;i<a.length;i++)System.out.print(a[i]);System.out.println();}; void solve() throws NumberFormatException, IOException{ final ContestScanner in = new ContestScanner(); Writer out = new Writer(); int n = in.nextInt(); int m = in.nextInt(); int st = in.nextInt(); int dt = in.nextInt(); List<Edge>[] node = new List[n]; int[] dst = new int[n]; for(int i=0; i<n; i++) node[i] = new ArrayList<>(); int longest = 0; for(int i=0; i<m; i++){ int l = in.nextInt(); int[] s = new int[l]; int[] w = new int[l-1]; for(int j=0; j<l; j++){ s[j] = in.nextInt(); } int sum = 0; for(int j=0; j<l-1; j++){ w[j] = in.nextInt(); sum += w[j]; node[s[j]].add(new Edge(s[j+1], w[j], s[0], sum)); } sum = 0; for(int j=l-2; j>=0; j--){ sum += w[j]; node[s[j+1]].add(new Edge(s[j], w[j], s[l-1], sum)); } longest = Math.max(longest, sum); } final int inf = Integer.MAX_VALUE; for(int i=0; i<n; i++) dst[i] = inf; Queue<P> qu0 = new PriorityQueue<>(); dst[dt] = 0; qu0.add(new P(dt, 0)); BitSet used = new BitSet(n); while(!qu0.isEmpty()){ P p = qu0.poll(); if(used.get(p.id)) continue; used.set(p.id); dst[p.id] = p.d; for(Edge e: node[p.id]){ if(used.get(e.to)) continue; qu0.add(new P(e.to, p.d+e.d)); } } used.clear(); Queue<Pos> qu = new PriorityQueue<>(); qu.add(new Pos(dt, 0, 0)); // int[] maxd = new int[n]; // int[] maxt = new int[n]; // for(int i=0; i<n; i++){ // maxd[i] = inf; // maxt[i] = inf; // } int ans = inf; while(!qu.isEmpty()){ Pos p = qu.poll(); // if(maxd[p.id]<=p.d && maxt[p.id]<=p.max) continue; // maxd[p.id] = p.d; // maxt[p.id] = p.max; if(used.get(p.id)) continue; used.set(p.id); if(p.id == st){ ans = Math.min(ans, p.d); continue; } for(Edge e: node[p.id]){ qu.add(new Pos(e.to, p.d+e.d, e.ld+dst[e.lst])); } } System.out.println(ans); } } class P implements Comparable<P>{ int id, d; P(int id, int d){ this.id = id; this.d = d; } @Override public int compareTo(P o) { return d-o.d; } } class Pos implements Comparable<Pos>{ int id, d; Pos(int id, int d, int max){ this.id = id; this.d = Math.max(d, max); } @Override public int compareTo(Pos o) { return d-o.d; } } class Edge{ int to, d; int lst, ld; Edge(int to, int d, int lst, int ld){ this.to = to; this.d = d; this.lst = lst; this.ld = ld; } } class MultiSet<T> extends HashMap<T, Integer>{ @Override public Integer get(Object key){return containsKey(key)?super.get(key):0;} public void add(T key,int v){put(key,get(key)+v);} public void add(T key){put(key,get(key)+1);} public void sub(T key) {final int v=get(key);if(v==1)remove(key);else put(key,v-1);} } class Timer{ long time; public void set(){time=System.currentTimeMillis();} public long stop(){return time=System.currentTimeMillis()-time;} public void print() {System.out.println("Time: "+(System.currentTimeMillis()-time)+"ms");} @Override public String toString(){return"Time: "+time+"ms";} } class Writer extends PrintWriter{ public Writer(String filename)throws IOException {super(new BufferedWriter(new FileWriter(filename)));} public Writer()throws IOException{super(System.out);} } class ContestScanner { private InputStreamReader in;private int c=-2; public ContestScanner()throws IOException {in=new InputStreamReader(System.in);} public ContestScanner(String filename)throws IOException {in=new InputStreamReader(new FileInputStream(filename));} public String nextToken()throws IOException { StringBuilder sb=new StringBuilder(); while((c=in.read())!=-1&&Character.isWhitespace(c)); while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();} return sb.toString(); } public String readLine()throws IOException{ StringBuilder sb=new StringBuilder();if(c==-2)c=in.read(); while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();} return sb.toString(); } public long nextLong()throws IOException,NumberFormatException {return Long.parseLong(nextToken());} public int nextInt()throws NumberFormatException,IOException {return(int)nextLong();} public double nextDouble()throws NumberFormatException,IOException {return Double.parseDouble(nextToken());} }
Submission Info
Submission Time | |
---|---|
Task | C - メンテナンス明け |
User | threepipes_s |
Language | Java (OpenJDK 1.7.0) |
Score | 100 |
Code Size | 5206 Byte |
Status | AC |
Exec Time | 1093 ms |
Memory | 44396 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Subtask1 | Subtask2 | ||||
---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask1 | small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05 |
Subtask2 | large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
large/20_large-00 | AC | 1010 ms | 43580 KB |
large/20_large-01 | AC | 1049 ms | 43568 KB |
large/20_large-02 | AC | 1093 ms | 44112 KB |
large/20_large-03 | AC | 1004 ms | 44176 KB |
large/20_large-04 | AC | 1092 ms | 44396 KB |
large/31_max_large | AC | 993 ms | 41440 KB |
small/00_sample00 | AC | 468 ms | 22472 KB |
small/00_sample01 | AC | 428 ms | 22544 KB |
small/00_sample02 | AC | 342 ms | 22536 KB |
small/10_small-0000 | AC | 491 ms | 23000 KB |
small/10_small-0001 | AC | 457 ms | 23340 KB |
small/10_small-0002 | AC | 409 ms | 23068 KB |
small/10_small-0003 | AC | 402 ms | 23400 KB |
small/10_small-0004 | AC | 383 ms | 23368 KB |
small/10_small-0005 | AC | 385 ms | 23288 KB |
small/10_small-0006 | AC | 387 ms | 23364 KB |
small/10_small-0007 | AC | 379 ms | 23256 KB |
small/10_small-0008 | AC | 402 ms | 23052 KB |
small/10_small-0009 | AC | 486 ms | 23080 KB |
small/10_small-0010 | AC | 402 ms | 22928 KB |
small/10_small-0011 | AC | 412 ms | 23356 KB |
small/10_small-0012 | AC | 385 ms | 23328 KB |
small/10_small-0013 | AC | 385 ms | 23272 KB |
small/10_small-0014 | AC | 395 ms | 23328 KB |
small/10_small-0015 | AC | 409 ms | 23352 KB |
small/10_small-0016 | AC | 451 ms | 23136 KB |
small/10_small-0017 | AC | 447 ms | 23360 KB |
small/10_small-0018 | AC | 442 ms | 23060 KB |
small/10_small-0019 | AC | 411 ms | 23032 KB |
small/30_max_small | AC | 379 ms | 22664 KB |
small/40_simple_0000 | AC | 344 ms | 22416 KB |
small/40_simple_0001 | AC | 357 ms | 22480 KB |
small/40_simple_0002 | AC | 335 ms | 22588 KB |
small/40_simple_0003 | AC | 335 ms | 22536 KB |
small/40_simple_0004 | AC | 348 ms | 22516 KB |
small/40_simple_0005 | AC | 370 ms | 22500 KB |
small/40_simple_0006 | AC | 372 ms | 22408 KB |
small/40_simple_0007 | AC | 361 ms | 22528 KB |
small/40_simple_0008 | AC | 414 ms | 22496 KB |
small/40_simple_0009 | AC | 399 ms | 22400 KB |
small/40_simple_0010 | AC | 420 ms | 22408 KB |
small/40_simple_0011 | AC | 378 ms | 22472 KB |
small/40_simple_0012 | AC | 434 ms | 22520 KB |
small/40_simple_0013 | AC | 403 ms | 22516 KB |
small/40_simple_0014 | AC | 382 ms | 22420 KB |
small/40_simple_0015 | AC | 426 ms | 22364 KB |
small/40_simple_0016 | AC | 393 ms | 22528 KB |
small/40_simple_0017 | AC | 340 ms | 22536 KB |
small/40_simple_0018 | AC | 377 ms | 22532 KB |
small/40_simple_0019 | AC | 362 ms | 22572 KB |
small/90_dijkstra_killer_00 | AC | 339 ms | 22540 KB |
small/90_dijkstra_killer_01 | AC | 375 ms | 22352 KB |
small/91_tayama_killer_00 | AC | 385 ms | 22576 KB |
small/91_tayama_killer_01 | AC | 345 ms | 22416 KB |
small/91_tayama_killer_02 | AC | 334 ms | 22524 KB |
small/91_tayama_killer_03 | AC | 343 ms | 22472 KB |
small/91_tayama_killer_04 | AC | 333 ms | 22504 KB |
small/91_tayama_killer_05 | AC | 370 ms | 22440 KB |