Submission #1026795
Source Code Expand
using System; using System.Text; using System.Collections.Generic; class Solve{ public Solve(){} StringBuilder sb; public static int Main(){ new Solve().Run(); return 0; } void Run(){ sb = new StringBuilder(); Calc(); Console.Write(sb.ToString()); } void Calc(){ string[] str = Console.ReadLine().Split(' '); int N = int.Parse(str[0]); int M = int.Parse(str[1]); int S = int.Parse(str[2]); int G = int.Parse(str[3]); List<int>[] station = new List<int>[M]; List<int>[] cost = new List<int>[M]; for(int i=0;i<M;i++){ int L = int.Parse(Console.ReadLine()); str = Console.ReadLine().Split(' '); station[i] = new List<int>(); for(int j=0;j<L;j++){ station[i].Add(int.Parse(str[j])); } str = Console.ReadLine().Split(' '); cost[i] = new List<int>(); for(int j=0;j<L-1;j++){ cost[i].Add(int.Parse(str[j])); } } List<int> f = new List<int>(); List<int> t = new List<int>(); List<long> c = new List<long>(); for(int i=0;i<M;i++){ for(int j=0;j<cost[i].Count;j++){ f.Add(station[i][j+1]); t.Add(station[i][j]); c.Add(cost[i][j]); } for(int j=cost[i].Count-1;j>=0;j--){ f.Add(station[i][j]); t.Add(station[i][j+1]); c.Add(cost[i][j]); } } Dijkstra D = new Dijkstra(f.ToArray(),t.ToArray(),c.ToArray(),N,G); List<long> s = new List<long>(); for(int i=0;i<M;i++){ long sc = D.GetCost(station[i][0]); for(int j=0;j<cost[i].Count;j++){ sc += cost[i][j]; s.Add(sc); } sc = D.GetCost(station[i][station[i].Count-1]); for(int j=cost[i].Count-1;j>=0;j--){ sc += cost[i][j]; s.Add(sc); } } Dijkstra2 D2 = new Dijkstra2(t.ToArray(),f.ToArray(),c.ToArray(),s.ToArray(),N,G); sb.Append(D2.GetCost(S)+"\n"); } } struct Edge2{ public Vertex2 v; public long cost; public Edge2(Vertex2 v0,long c){ v = v0; cost = c; } } class Vertex2{ public bool finished; public List<Vertex2> edges; public List<long> costs; public List<long> sleepcosts; public long cost; public void AddEdge(Vertex2 v,long c,long s){ edges.Add(v); costs.Add(c); sleepcosts.Add(s); } public Vertex2(){ edges = new List<Vertex2>(); costs = new List<long>(); sleepcosts = new List<long>(); cost = -1; finished = false; } } class Dijkstra2{ int E; Vertex2[] point; Vertex2 S; public long GetCost(int i){ return point[i].cost; } public Dijkstra2(int[] f,int[] t,long[] cost,long[] sleepcost,int n,int s){ point = new Vertex2[n]; for(int i=0;i<n;i++){ point[i] = new Vertex2(); } E = f.Length; for(int i=0;i<E;i++){ point[f[i]].AddEdge(point[t[i]],cost[i],sleepcost[i]); } S = point[s]; calc(); } void calc(){ Heap2 H = new Heap2(2*E); S.cost = 0; H.push(new Edge2(S,0)); while(!H.Empty()){ Vertex2 v = H.pop().v; if(v.finished){ continue; } v.finished = true; for(int i=0;i<v.edges.Count;i++){ Vertex2 vi = v.edges[i]; if(vi.cost == -1 || vi.cost > Math.Max(v.costs[i]+v.cost,v.sleepcosts[i])){ vi.cost = Math.Max(v.costs[i]+v.cost,v.sleepcosts[i]); H.push(new Edge2(vi,vi.cost)); } } } } } class Heap2{ public int size; Edge2[] obj; public Heap2(int maxsize){ size = 0; obj = new Edge2[maxsize]; } public void push(Edge2 a){ int i = size; size++; while(i > 0){ int p = (i - 1)/2; if(obj[p].cost <= a.cost){ obj[i] = a; break; } obj[i] = obj[p]; i = p; } if(i == 0){ obj[0] = a; } } public bool Empty(){ return size == 0; } public Edge2 pop(){ Edge2 t = obj[0]; int i = 0; size--; while(2*i+1 < size){ int p = 2*i+1; if(p+1 < size && obj[p+1].cost < obj[p].cost){ p++; } if(obj[p].cost < obj[size].cost){ obj[i] = obj[p]; i = p; } else{ obj[i] = obj[size]; break; } } if(2*i+1 >= size){ obj[i] = obj[size]; } return t; } } struct Edge{ public Vertex v; public long cost; public Edge(Vertex v0,long c){ v = v0; cost = c; } } class Vertex{ public bool finished; public List<Vertex> edges; public List<long> costs; public long cost; public void AddEdge(Vertex v,long c){ edges.Add(v); costs.Add(c); } public Vertex(){ edges = new List<Vertex>(); costs = new List<long>(); cost = -1; finished = false; } } class Dijkstra{ int E; Vertex[] point; Vertex S; public long GetCost(int i){ return point[i].cost; } public Dijkstra(int[] f,int[] t,long[] cost,int n,int s){ point = new Vertex[n]; for(int i=0;i<n;i++){ point[i] = new Vertex(); } E = f.Length; for(int i=0;i<E;i++){ point[f[i]].AddEdge(point[t[i]],cost[i]); } S = point[s]; calc(); } void calc(){ Heap H = new Heap(2*E); S.cost = 0; H.push(new Edge(S,0)); while(!H.Empty()){ Vertex v = H.pop().v; if(v.finished){ continue; } v.finished = true; for(int i=0;i<v.edges.Count;i++){ Vertex vi = v.edges[i]; if(vi.cost == -1 || vi.cost > v.costs[i]+v.cost){ vi.cost = v.costs[i]+v.cost; H.push(new Edge(vi,vi.cost)); } } } } } class Heap{ public int size; Edge[] obj; public Heap(int maxsize){ size = 0; obj = new Edge[maxsize]; } public void push(Edge a){ int i = size; size++; while(i > 0){ int p = (i - 1)/2; if(obj[p].cost <= a.cost){ obj[i] = a; break; } obj[i] = obj[p]; i = p; } if(i == 0){ obj[0] = a; } } public bool Empty(){ return size == 0; } public Edge pop(){ Edge t = obj[0]; int i = 0; size--; while(2*i+1 < size){ int p = 2*i+1; if(p+1 < size && obj[p+1].cost < obj[p].cost){ p++; } if(obj[p].cost < obj[size].cost){ obj[i] = obj[p]; i = p; } else{ obj[i] = obj[size]; break; } } if(2*i+1 >= size){ obj[i] = obj[size]; } return t; } }
Submission Info
Submission Time | |
---|---|
Task | C - メンテナンス明け |
User | leign |
Language | C# (Mono 3.2.1.0) |
Score | 100 |
Code Size | 7926 Byte |
Status | AC |
Exec Time | 218 ms |
Memory | 39824 KB |
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 | 218 ms | 39784 KB |
large/20_large-01 | AC | 217 ms | 39820 KB |
large/20_large-02 | AC | 216 ms | 39824 KB |
large/20_large-03 | AC | 216 ms | 39592 KB |
large/20_large-04 | AC | 218 ms | 39692 KB |
large/31_max_large | AC | 166 ms | 37728 KB |
small/00_sample00 | AC | 80 ms | 8000 KB |
small/00_sample01 | AC | 81 ms | 7996 KB |
small/00_sample02 | AC | 79 ms | 7948 KB |
small/10_small-0000 | AC | 82 ms | 8408 KB |
small/10_small-0001 | AC | 81 ms | 8368 KB |
small/10_small-0002 | AC | 80 ms | 8252 KB |
small/10_small-0003 | AC | 81 ms | 8248 KB |
small/10_small-0004 | AC | 83 ms | 8364 KB |
small/10_small-0005 | AC | 82 ms | 8372 KB |
small/10_small-0006 | AC | 81 ms | 8336 KB |
small/10_small-0007 | AC | 87 ms | 8372 KB |
small/10_small-0008 | AC | 83 ms | 8352 KB |
small/10_small-0009 | AC | 87 ms | 8368 KB |
small/10_small-0010 | AC | 85 ms | 8252 KB |
small/10_small-0011 | AC | 83 ms | 8356 KB |
small/10_small-0012 | AC | 83 ms | 8364 KB |
small/10_small-0013 | AC | 83 ms | 8372 KB |
small/10_small-0014 | AC | 85 ms | 8364 KB |
small/10_small-0015 | AC | 84 ms | 8336 KB |
small/10_small-0016 | AC | 82 ms | 8240 KB |
small/10_small-0017 | AC | 83 ms | 8360 KB |
small/10_small-0018 | AC | 82 ms | 8352 KB |
small/10_small-0019 | AC | 81 ms | 8320 KB |
small/30_max_small | AC | 83 ms | 8292 KB |
small/40_simple_0000 | AC | 81 ms | 7952 KB |
small/40_simple_0001 | AC | 82 ms | 8064 KB |
small/40_simple_0002 | AC | 80 ms | 8064 KB |
small/40_simple_0003 | AC | 79 ms | 7952 KB |
small/40_simple_0004 | AC | 82 ms | 8056 KB |
small/40_simple_0005 | AC | 79 ms | 7936 KB |
small/40_simple_0006 | AC | 102 ms | 7952 KB |
small/40_simple_0007 | AC | 79 ms | 7968 KB |
small/40_simple_0008 | AC | 80 ms | 7936 KB |
small/40_simple_0009 | AC | 80 ms | 7928 KB |
small/40_simple_0010 | AC | 82 ms | 7948 KB |
small/40_simple_0011 | AC | 81 ms | 7940 KB |
small/40_simple_0012 | AC | 81 ms | 8024 KB |
small/40_simple_0013 | AC | 81 ms | 7948 KB |
small/40_simple_0014 | AC | 82 ms | 8056 KB |
small/40_simple_0015 | AC | 85 ms | 8088 KB |
small/40_simple_0016 | AC | 81 ms | 7956 KB |
small/40_simple_0017 | AC | 82 ms | 7996 KB |
small/40_simple_0018 | AC | 81 ms | 8004 KB |
small/40_simple_0019 | AC | 83 ms | 8064 KB |
small/90_dijkstra_killer_00 | AC | 83 ms | 7944 KB |
small/90_dijkstra_killer_01 | AC | 85 ms | 8076 KB |
small/91_tayama_killer_00 | AC | 83 ms | 7948 KB |
small/91_tayama_killer_01 | AC | 81 ms | 7956 KB |
small/91_tayama_killer_02 | AC | 81 ms | 8052 KB |
small/91_tayama_killer_03 | AC | 84 ms | 8064 KB |
small/91_tayama_killer_04 | AC | 81 ms | 8004 KB |
small/91_tayama_killer_05 | AC | 80 ms | 7996 KB |