Submission #1962560
Source Code Expand
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; class Main{ static class Dijkstra{ class Edge{ int to,cost; Edge(int t,int c){to=t;cost=c;} } int N; List<Edge>[] G; Dijkstra(int N){ this.N=N; G = new ArrayList[N]; for(int i=0;i<N;++i)G[i] = new ArrayList<>(); } void addEdge(int from,int to,int cost){ G[from].add(new Edge(to, cost)); } int[] dijkstra(int s){ class QueNode{ int v,w; QueNode(int v,int w){this.v=v;this.w=w;} } int[] dis = new int[N]; Arrays.fill(dis, Integer.MAX_VALUE); dis[s] = 0; PriorityQueue<QueNode> que = new PriorityQueue<>((a,b) -> a.w - b.w); que.add(new QueNode(s,0)); while(!que.isEmpty()){ QueNode node = que.poll(); if(dis[node.v] < node.w)continue; for(Edge e : G[node.v]){ if(dis[e.to] > dis[node.v] + e.cost){ dis[e.to] = dis[node.v]+e.cost; que.add(new QueNode(e.to, dis[e.to])); } } } return dis; } } static class Edge{ int cost; int sleepCost; int endPoint; int to; Edge(int end,int scost,int to){ this.endPoint=end; this.sleepCost=scost; this.to=to; } } static List<Edge>[] edgeList; static boolean[] used; static boolean dfs(int s,int v,int c){ used[s]=true; if(s==v)return true; for(Edge e : edgeList[s]){ if(e.cost > c)continue; if(used[e.to])continue; if(dfs(e.to,v,c))return true; } return false; } public static void main(String[] args){ Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int M = scan.nextInt(); int src=scan.nextInt(); int dst=scan.nextInt(); Dijkstra djk = new Dijkstra(N); edgeList = new ArrayList[N]; for(int i=0;i<N;++i)edgeList[i] = new ArrayList<>(); while(M-->0){ int L = scan.nextInt(); int[] s = new int[L]; int[] w = new int[L-1]; for(int i=0;i<L;++i)s[i] = scan.nextInt(); for(int i=0;i<L-1;++i)w[i] = scan.nextInt(); for(int i=0;i<L-1;++i){ djk.addEdge(s[i], s[i+1], w[i]); djk.addEdge(s[i+1], s[i], w[i]); } int sleepcost=0; for(int i=0;i<L-1;++i)sleepcost += w[i]; for(int i=0;i<L-1;++i){ edgeList[s[i]].add(new Edge(s[L-1],sleepcost,s[i+1])); sleepcost -= w[i]; } sleepcost=0; for(int i=0;i<L-1;++i)sleepcost += w[i]; for(int i=L-1;i>0;--i){ edgeList[s[i]].add(new Edge(s[0], sleepcost,s[i-1])); sleepcost -=w[i-1]; } } int[] srcdis = djk.dijkstra(src); int[] dstdis = djk.dijkstra(dst); for(int i=0;i<N;++i){ for(Edge e : edgeList[i]){ e.cost = srcdis[i]+e.sleepCost + dstdis[e.endPoint]; } } used = new boolean[N]; int left=0; int right = Integer.MAX_VALUE/2; while(true){ Arrays.fill(used, false); int center=(left+right+1)/2; if(dfs(src,dst,center)){ right = center; }else{ left = center; } if(right-left == 1)break; } System.out.println(right); // class QueNode{ // int v,w; // QueNode(int v,int w){this.v=v;this.w=w;} // } // PriorityQueue<QueNode> que = new PriorityQueue<>((a,b) -> a.w-b.w); // int[] dis = new int[N]; // Arrays.fill(dis, Integer.MAX_VALUE); // dis[src] = 0; // que.add(new QueNode(src, 0)); // while(!que.isEmpty()){ // QueNode node = que.poll(); // if(node.w > dis[node.v])continue; // for(Edge e : edgeList[node.v]){ // int cost = Math.max(dis[node.v], e.cost); // if(cost < dis[e.to]){ // dis[e.to] = cost; // que.add(new QueNode(e.to, cost)); // } // } // } //System.out.println(dis[dst]); } }
Submission Info
Submission Time | |
---|---|
Task | C - メンテナンス明け |
User | inmir |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 4862 Byte |
Status | WA |
Exec Time | 805 ms |
Memory | 80196 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 | 0 / 50 | 0 / 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 | WA | 805 ms | 76980 KB |
large/20_large-01 | WA | 782 ms | 78576 KB |
large/20_large-02 | AC | 799 ms | 80196 KB |
large/20_large-03 | WA | 712 ms | 75244 KB |
large/20_large-04 | WA | 771 ms | 77880 KB |
large/31_max_large | AC | 540 ms | 48064 KB |
small/00_sample00 | AC | 187 ms | 26068 KB |
small/00_sample01 | AC | 191 ms | 25940 KB |
small/00_sample02 | AC | 177 ms | 26196 KB |
small/10_small-0000 | WA | 235 ms | 24580 KB |
small/10_small-0001 | AC | 218 ms | 26868 KB |
small/10_small-0002 | AC | 212 ms | 26312 KB |
small/10_small-0003 | WA | 223 ms | 26572 KB |
small/10_small-0004 | AC | 228 ms | 24708 KB |
small/10_small-0005 | WA | 228 ms | 24644 KB |
small/10_small-0006 | AC | 227 ms | 26356 KB |
small/10_small-0007 | AC | 225 ms | 26340 KB |
small/10_small-0008 | AC | 227 ms | 24740 KB |
small/10_small-0009 | WA | 239 ms | 23216 KB |
small/10_small-0010 | AC | 217 ms | 24732 KB |
small/10_small-0011 | WA | 221 ms | 24496 KB |
small/10_small-0012 | WA | 230 ms | 25100 KB |
small/10_small-0013 | WA | 226 ms | 26616 KB |
small/10_small-0014 | AC | 223 ms | 26660 KB |
small/10_small-0015 | AC | 223 ms | 26892 KB |
small/10_small-0016 | WA | 230 ms | 26508 KB |
small/10_small-0017 | WA | 241 ms | 24860 KB |
small/10_small-0018 | AC | 226 ms | 26408 KB |
small/10_small-0019 | AC | 223 ms | 28328 KB |
small/30_max_small | AC | 206 ms | 24884 KB |
small/40_simple_0000 | AC | 173 ms | 24788 KB |
small/40_simple_0001 | AC | 190 ms | 26188 KB |
small/40_simple_0002 | AC | 170 ms | 26580 KB |
small/40_simple_0003 | AC | 184 ms | 24148 KB |
small/40_simple_0004 | AC | 182 ms | 26576 KB |
small/40_simple_0005 | AC | 185 ms | 24020 KB |
small/40_simple_0006 | AC | 191 ms | 24276 KB |
small/40_simple_0007 | AC | 175 ms | 26068 KB |
small/40_simple_0008 | AC | 189 ms | 24788 KB |
small/40_simple_0009 | AC | 176 ms | 26060 KB |
small/40_simple_0010 | AC | 193 ms | 26708 KB |
small/40_simple_0011 | AC | 176 ms | 25928 KB |
small/40_simple_0012 | AC | 178 ms | 25936 KB |
small/40_simple_0013 | AC | 178 ms | 24148 KB |
small/40_simple_0014 | AC | 189 ms | 24008 KB |
small/40_simple_0015 | AC | 186 ms | 24660 KB |
small/40_simple_0016 | AC | 176 ms | 26324 KB |
small/40_simple_0017 | AC | 178 ms | 28500 KB |
small/40_simple_0018 | AC | 177 ms | 24016 KB |
small/40_simple_0019 | AC | 188 ms | 24656 KB |
small/90_dijkstra_killer_00 | AC | 195 ms | 25940 KB |
small/90_dijkstra_killer_01 | AC | 175 ms | 28500 KB |
small/91_tayama_killer_00 | AC | 179 ms | 25040 KB |
small/91_tayama_killer_01 | AC | 172 ms | 24660 KB |
small/91_tayama_killer_02 | AC | 174 ms | 24532 KB |
small/91_tayama_killer_03 | AC | 180 ms | 25940 KB |
small/91_tayama_killer_04 | AC | 178 ms | 28116 KB |
small/91_tayama_killer_05 | AC | 190 ms | 24148 KB |