結果

問題 No.845 最長の切符
ユーザー spielatoon
提出日時 2019-07-11 15:48:56
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,362 bytes
コンパイル時間 4,565 ms
コンパイル使用メモリ 107,008 KB
実行使用メモリ 27,776 KB
最終ジャッジ日時 2024-11-07 19:50:11
合計ジャッジ時間 7,315 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 1 -- * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;

public class Hello{
    
    public static Station[] stations;
    public static void Main(){
        //標準入力の読み込み
        var line = System.Console.ReadLine().Split(' ');
        int N = int.Parse(line[0]);
        int M = int.Parse(line[1]);
        
        //駅の配列を作成
        stations = new Station[N];
        for(int i=0;i<N;i++){
            stations[i] = new Station();
        }
        
        //駅の情報を読み込み
        int A = 0;
        int B = 0;
        int dis = 0;
        for(int i=0;i<M;i++){
            line = System.Console.ReadLine().Split(' ');
            A = int.Parse(line[0])-1;
            B = int.Parse(line[1])-1;
            dis = int.Parse(line[2]);
            stations[A].next.Add(new NextStation(B,dis));
            stations[B].next.Add(new NextStation(A,dis));
        }
        
        //それぞれの駅を始発とした終着までの距離を算出する
        var arr = new int[N];
        for(int i=0;i<N;i++){
            arr[i] = CalcDistance(i,new List<int>(),0);
        }
        
        //最大値を出力
        System.Console.WriteLine(arr.Max());
    }
    private static int CalcDistance(int now, List<int> via, int dist){
        //現在の駅から移動可能な駅を書き出す
        var canMoveList = new List<NextStation>();
        foreach(var ns in stations[now].next){
            if(!via.Contains(ns.id)){
                canMoveList.Add(ns);
            }
        }
        
        //移動可能な駅が存在しない場合はここを終着とする
        int cnt = canMoveList.Count;
        if(cnt==0){
            return dist;
        }
        
        //移動可能な駅へ移動して距離の最大値を取得する
        var arr = new int[cnt];
        for(int i=0;i<cnt;i++){
            var newVia = new List<int>(via);
            newVia.Add(now);
            arr[i] = CalcDistance(canMoveList[i].id,newVia,dist+canMoveList[i].distance);
        }
        return arr.Max();
    }
}
public class Station{
    public List<NextStation> next = new List<NextStation>();
}
public class NextStation{
    public int id;
    public int distance;
    public NextStation(int a, int b){
        this.id = a;
        this.distance = b;
    }
}
0