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
AC × 52
AC × 6
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