結果

問題 No.92 逃走経路
ユーザー mban
提出日時 2017-01-12 07:13:04
言語 C#
結果
AC  
実行時間 3950 ms
コード長 3132 Byte
コンパイル時間 348 ms
使用メモリ 40476 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt AC 727 ms
36572 KB
sample01.txt AC 36 ms
17744 KB
sample02.txt AC 35 ms
15712 KB
test01.txt AC 35 ms
17760 KB
test02.txt AC 35 ms
15716 KB
test03.txt AC 102 ms
15752 KB
test04.txt AC 49 ms
17792 KB
test05.txt AC 49 ms
15756 KB
test06.txt AC 54 ms
24664 KB
test07.txt AC 83 ms
37500 KB
test08.txt AC 3278 ms
39400 KB
test09.txt AC 2154 ms
37320 KB
test10.txt AC 3950 ms
40476 KB
test11.txt AC 59 ms
19956 KB
test12.txt AC 431 ms
36168 KB
test13.txt AC 947 ms
36884 KB
test14.txt AC 370 ms
34748 KB
test15.txt AC 754 ms
34280 KB
test16.txt AC 329 ms
24716 KB
test17.txt AC 131 ms
20196 KB
テストケース一括ダウンロード

ソースコード

diff #
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;

class Program
{
    static private Magatro M = new Magatro();
    static private void Main(string[]args)
    {
        M.Scan();
        M.Solve();
    }
}
public class Scanner
{
    private string[] S;
    private int Index;
    private char Separator;
    public Scanner(char separator = ' ')
    {
        Index = 0;
        Separator = separator;
    }
    private string[] Line()
    {
        return Console.ReadLine().Split(Separator);
    }
    public string Next()
    {
        string result;
        if (S == null || Index >= S.Length)
        {
            S = Line();
            Index = 0;
        }
        result = S[Index];
        Index++;
        return result;
    }
    public int NextInt()
    {
        return int.Parse(Next());
    }
    public double NextDouble()
    {
        return double.Parse(Next());
    }
    public long NextLong()
    {
        return long.Parse(Next());
    }
}
public class Magatro
{
    private int N, M, K;
    private int[] d;
    private List<int>[] Load;
    private List<int>[] Fee;
    private HashSet<int> Anser = new HashSet<int>();
    public void Scan()
    {
        Scanner sc = new Scanner();
        N = sc.NextInt();
        M = sc.NextInt();
        K = sc.NextInt();
        Load = new List<int>[N];
        Fee = new List<int>[N];
        for(int i = 0; i < N; i++)
        {
            Load[i] = new List<int>();
            Fee[i] = new List<int>();
        }
        for (int i = 0; i < M; i++)
        {
            int a = sc.NextInt();
            int b = sc.NextInt();
            int c = sc.NextInt();
            Load[a - 1].Add(b-1);
            Load[b - 1].Add(a-1);
            Fee[a - 1].Add(c);
            Fee[b - 1].Add(c);
        }
        d = new int[K];
        for(int i = 0; i < K; i++)
        {
            d[i] = sc.NextInt();
        }
    }
    public void Solve()
    {
        for(int i = 0; i < N; i++)
        {
            HashSet<int>[] to = new HashSet<int>[K];
            for(int j = 0; j < K; j++)
            {
                to[j] = new HashSet<int>();
                if (j == 0)
                {
                    for (int k = 0; k < Load[i].Count; k++)
                    {
                        if (Fee[i][k] == d[j]) to[j].Add(Load[i][k]);
                    }
                }
                else
                {
                    foreach(int k in to[j - 1])
                    {
                        for(int l = 0; l < Load[k].Count; l++)
                        {
                            if (Fee[k][l] == d[j]) to[j].Add(Load[k][l]);
                        }
                    }
                }
            }
            foreach(int a in to[K - 1])
            {
                Anser.Add(a+1);
            }

        }
        int[] ans = Anser.ToArray();
        Array.Sort(ans);
        Console.WriteLine(ans.Length);
        Console.WriteLine(string.Join(" ", ans));
    }
}
0