結果
問題 |
No.807 umg tours
|
ユーザー |
|
提出日時 | 2019-04-03 16:17:45 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,766 bytes |
コンパイル時間 | 4,305 ms |
コンパイル使用メモリ | 112,004 KB |
実行使用メモリ | 823,864 KB |
最終ジャッジ日時 | 2024-11-23 19:24:05 |
合計ジャッジ時間 | 31,265 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 TLE * 1 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; using System.Text; using static System.Console; using static System.Math; namespace AtTest.yukicoder { class _807 { static void Main(string[] args) { Method(args); ReadLine(); } static void Method(string[] args) { int[] nm = ReadInts(); int n = nm[0]; int m = nm[1]; List<int[]>[] graph = new List<int[]>[n]; for (int i = 0; i < n; i++) graph[i] = new List<int[]>(); for (int i = 0; i < m; i++) { int[] abc = ReadInts(); int a = abc[0] - 1; int b = abc[1] - 1; int c = abc[2]; graph[a].Add(new int[2] { b, c }); graph[b].Add(new int[2] { a, c }); } long[,] dists = new long[n, 2]; for (int i = 0; i < n; i++) { dists[i, 0] = long.MaxValue / 8; dists[i, 1] = long.MaxValue / 8; } Queue<long[]> queue = new Queue<long[]>(); queue.Enqueue(new long[3] { 0, 0, 0 }); while (queue.Count > 0) { long[] val = queue.Dequeue(); if (dists[val[0], val[1]] <= val[2]) continue; dists[val[0], val[1]] = val[2]; for (int i = 0; i < graph[val[0]].Count; i++) { int[] to = graph[val[0]][i]; if (val[2] + to[1] < dists[to[0], val[1]]) { queue.Enqueue( new long[3] { to[0], val[1], val[2] + to[1] }); } if (val[1] == 0 && val[2] < dists[to[0], 1]) { queue.Enqueue( new long[3] { to[0], 1, val[2] }); } } } WriteLine(0); for (int i = 1; i < n; i++) { WriteLine(dists[i, 0] + dists[i, 1]); } } private static string Read() { return ReadLine(); } private static int ReadInt() { return int.Parse(Read()); } private static long ReadLong() { return long.Parse(Read()); } private static double ReadDouble() { return double.Parse(Read()); } private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); } private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); } private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); } } }