Submission #1026632
Source Code Expand
using System; using System.Text; using System.Collections.Generic; class Solve{ List<Edge2>[] e; int G; long[] dp; bool[] df; bool[] finished; 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]); 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])); } } Dijkstra D; { 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]); f.Add(station[i][j+1]); t.Add(station[i][j+1]); t.Add(station[i][j]); c.Add(cost[i][j]); c.Add(cost[i][j]); } } D = new Dijkstra(f.ToArray(),t.ToArray(),c.ToArray(),N,G); } e = new List<Edge2>[N]; for(int i=0;i<N;i++){ e[i] = new List<Edge2>(); } for(int i=0;i<M;i++){ long c = D.GetCost(station[i][0]); for(int j=0;j<cost[i].Count;j++){ c += cost[i][j]; e[station[i][j+1]].Add(new Edge2(station[i][j],cost[i][j],c)); } c = D.GetCost(station[i][station[i].Count-1]); for(int j=cost[i].Count-1;j>=0;j--){ c += cost[i][j]; e[station[i][j]].Add(new Edge2(station[i][j+1],cost[i][j],c)); } } dp = new long[N]; df = new bool[N]; finished = new bool[N]; sb.Append(dfs(S)+"\n"); } long dfs(int n){ if(n == G){ return 0; } if(finished[n]){ return dp[n]; } df[n] = true; bool x = true; long min = -1; for(int i=0;i<e[n].Count;i++){ if(!df[e[n][i].t] && dfs(e[n][i].t) != -1){ long m = e[n][i].sleepcost > dfs(e[n][i].t) + e[n][i].cost ? e[n][i].sleepcost : dfs(e[n][i].t) + e[n][i].cost; min = (min == -1 || min > m) ? m : min; } else{ x = false; } } df[n] = false; dp[n] = min; finished[n] = x; return min; } } struct Edge2{ public int t; public long cost; public long sleepcost; public Edge2(int b,long c,long d){ t = b; cost = c; sleepcost = d; } } struct Vertex2{ public List<Edge2> e; } 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 | 0 |
Code Size | 6200 Byte |
Status | TLE |
Exec Time | 2556 ms |
Memory | 38668 KB |
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 | TLE | 2555 ms | 38412 KB |
large/20_large-01 | TLE | 2556 ms | 38588 KB |
large/20_large-02 | TLE | 2556 ms | 38668 KB |
large/20_large-03 | TLE | 2556 ms | 38316 KB |
large/20_large-04 | TLE | 2556 ms | 38424 KB |
large/31_max_large | AC | 148 ms | 33956 KB |
small/00_sample00 | AC | 83 ms | 7840 KB |
small/00_sample01 | AC | 80 ms | 7836 KB |
small/00_sample02 | AC | 83 ms | 7892 KB |
small/10_small-0000 | TLE | 2552 ms | 7996 KB |
small/10_small-0001 | TLE | 2553 ms | 7912 KB |
small/10_small-0002 | TLE | 2553 ms | 7912 KB |
small/10_small-0003 | TLE | 2552 ms | 7892 KB |
small/10_small-0004 | TLE | 2552 ms | 7916 KB |
small/10_small-0005 | TLE | 2552 ms | 7912 KB |
small/10_small-0006 | TLE | 2552 ms | 8004 KB |
small/10_small-0007 | TLE | 2552 ms | 8000 KB |
small/10_small-0008 | TLE | 2553 ms | 7952 KB |
small/10_small-0009 | TLE | 2552 ms | 7908 KB |
small/10_small-0010 | TLE | 2553 ms | 7872 KB |
small/10_small-0011 | TLE | 2552 ms | 7900 KB |
small/10_small-0012 | TLE | 2552 ms | 7920 KB |
small/10_small-0013 | TLE | 2552 ms | 7916 KB |
small/10_small-0014 | TLE | 2552 ms | 8012 KB |
small/10_small-0015 | TLE | 2552 ms | 8008 KB |
small/10_small-0016 | TLE | 2552 ms | 7916 KB |
small/10_small-0017 | TLE | 2552 ms | 7928 KB |
small/10_small-0018 | TLE | 2552 ms | 7920 KB |
small/10_small-0019 | TLE | 2552 ms | 7816 KB |
small/30_max_small | AC | 84 ms | 8056 KB |
small/40_simple_0000 | AC | 82 ms | 7908 KB |
small/40_simple_0001 | AC | 81 ms | 7896 KB |
small/40_simple_0002 | AC | 81 ms | 7840 KB |
small/40_simple_0003 | AC | 79 ms | 7948 KB |
small/40_simple_0004 | AC | 83 ms | 7848 KB |
small/40_simple_0005 | AC | 82 ms | 7848 KB |
small/40_simple_0006 | AC | 82 ms | 7844 KB |
small/40_simple_0007 | AC | 81 ms | 7936 KB |
small/40_simple_0008 | AC | 82 ms | 7852 KB |
small/40_simple_0009 | AC | 81 ms | 7892 KB |
small/40_simple_0010 | AC | 83 ms | 7856 KB |
small/40_simple_0011 | AC | 82 ms | 7904 KB |
small/40_simple_0012 | AC | 80 ms | 7824 KB |
small/40_simple_0013 | AC | 80 ms | 7828 KB |
small/40_simple_0014 | AC | 81 ms | 7904 KB |
small/40_simple_0015 | AC | 80 ms | 7844 KB |
small/40_simple_0016 | AC | 80 ms | 7904 KB |
small/40_simple_0017 | AC | 83 ms | 7856 KB |
small/40_simple_0018 | AC | 80 ms | 7964 KB |
small/40_simple_0019 | AC | 80 ms | 7968 KB |
small/90_dijkstra_killer_00 | AC | 81 ms | 7888 KB |
small/90_dijkstra_killer_01 | AC | 80 ms | 7824 KB |
small/91_tayama_killer_00 | AC | 81 ms | 7892 KB |
small/91_tayama_killer_01 | AC | 80 ms | 7836 KB |
small/91_tayama_killer_02 | AC | 80 ms | 7840 KB |
small/91_tayama_killer_03 | AC | 82 ms | 7852 KB |
small/91_tayama_killer_04 | AC | 80 ms | 7836 KB |
small/91_tayama_killer_05 | AC | 79 ms | 7904 KB |