#605425 (C#(csc)) No.1344 Typical Shortest Path Sum

提出ソース

結果

問題	No.1344 Typical Shortest Path Sum
ユーザー	さかぽん
提出日時	2021-01-16 13:32:51
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	74 ms / 2,000 ms
コード長	1,450 bytes
コンパイル時間	2,496 ms
コンパイル使用メモリ	110,292 KB
実行使用メモリ	23,804 KB
最終ジャッジ日時	2023-08-18 10:02:47
合計ジャッジ時間	11,330 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	71 ms 21,756 KB
testcase_01	AC	71 ms 23,716 KB
testcase_02	AC	70 ms 23,724 KB
testcase_03	AC	69 ms 21,824 KB
testcase_04	AC	69 ms 21,692 KB
testcase_05	AC	68 ms 21,652 KB
testcase_06	AC	69 ms 21,688 KB
testcase_07	AC	68 ms 21,784 KB
testcase_08	AC	68 ms 23,676 KB
testcase_09	AC	69 ms 21,624 KB
testcase_10	AC	68 ms 21,676 KB
testcase_11	AC	68 ms 21,644 KB
testcase_12	AC	69 ms 19,580 KB
testcase_13	AC	69 ms 23,776 KB
testcase_14	AC	69 ms 23,660 KB
testcase_15	AC	69 ms 21,680 KB
testcase_16	AC	69 ms 23,668 KB
testcase_17	AC	69 ms 21,676 KB
testcase_18	AC	70 ms 21,620 KB
testcase_19	AC	70 ms 23,608 KB
testcase_20	AC	70 ms 21,660 KB
testcase_21	AC	68 ms 21,728 KB
testcase_22	AC	70 ms 21,672 KB
testcase_23	AC	69 ms 21,780 KB
testcase_24	AC	70 ms 21,812 KB
testcase_25	AC	69 ms 21,644 KB
testcase_26	AC	69 ms 23,676 KB
testcase_27	AC	70 ms 21,680 KB
testcase_28	AC	70 ms 21,660 KB
testcase_29	AC	69 ms 23,724 KB
testcase_30	AC	70 ms 23,804 KB
testcase_31	AC	72 ms 21,756 KB
testcase_32	AC	70 ms 21,768 KB
testcase_33	AC	70 ms 21,720 KB
testcase_34	AC	69 ms 23,696 KB
testcase_35	AC	69 ms 23,764 KB
testcase_36	AC	68 ms 21,568 KB
testcase_37	AC	73 ms 23,712 KB
testcase_38	AC	69 ms 21,804 KB
testcase_39	AC	69 ms 21,568 KB
testcase_40	AC	73 ms 19,768 KB
testcase_41	AC	73 ms 21,640 KB
testcase_42	AC	72 ms 23,720 KB
testcase_43	AC	73 ms 23,660 KB
testcase_44	AC	73 ms 21,788 KB
testcase_45	AC	72 ms 21,672 KB
testcase_46	AC	72 ms 21,624 KB
testcase_47	AC	73 ms 23,784 KB
testcase_48	AC	73 ms 21,668 KB
testcase_49	AC	72 ms 23,664 KB
testcase_50	AC	71 ms 23,676 KB
testcase_51	AC	72 ms 21,732 KB
testcase_52	AC	72 ms 21,700 KB
testcase_53	AC	74 ms 23,708 KB
testcase_54	AC	71 ms 21,792 KB
testcase_55	AC	73 ms 21,796 KB
testcase_56	AC	73 ms 21,660 KB
testcase_57	AC	74 ms 21,628 KB
testcase_58	AC	72 ms 21,640 KB
testcase_59	AC	73 ms 23,736 KB
testcase_60	AC	71 ms 21,724 KB
testcase_61	AC	70 ms 19,596 KB
testcase_62	AC	73 ms 23,664 KB
testcase_63	AC	70 ms 23,744 KB
testcase_64	AC	71 ms 21,640 KB
testcase_65	AC	73 ms 21,608 KB
testcase_66	AC	72 ms 21,712 KB
testcase_67	AC	72 ms 21,720 KB
testcase_68	AC	70 ms 23,720 KB
testcase_69	AC	71 ms 23,752 KB
testcase_70	AC	70 ms 23,788 KB
testcase_71	AC	68 ms 21,648 KB
testcase_72	AC	68 ms 21,632 KB
testcase_73	AC	69 ms 21,856 KB
testcase_74	AC	69 ms 19,696 KB
testcase_75	AC	69 ms 21,688 KB
testcase_76	AC	71 ms 23,728 KB
testcase_77	AC	70 ms 19,576 KB
testcase_78	AC	70 ms 23,748 KB
testcase_79	AC	70 ms 21,688 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

using System;
using System.Linq;

class C
{
	static int[] Read() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
	static (int, int) Read2() { var a = Read(); return (a[0], a[1]); }
	static long[] ReadL() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
	static void Main()
	{
		var (n, m) = Read2();
		var es = Array.ConvertAll(new bool[m], _ => ReadL());

		var r = WarshallFloyd(n + 1, es, true).Item1;

		Console.WriteLine(string.Join("\n", r.Skip(1).Select(vs => vs.Where(v => v != long.MaxValue).Sum())));
	}

	public static Tuple<long[][], int[][]> WarshallFloyd(int n, long[][] es, bool directed)
	{
		var cs = Array.ConvertAll(new bool[n], i => Array.ConvertAll(new bool[n], _ => long.MaxValue));
		var inters = Array.ConvertAll(new bool[n], i => Array.ConvertAll(new bool[n], _ => -1));
		for (int i = 0; i < n; ++i) cs[i][i] = 0;

		foreach (var e in es)
		{
			cs[e[0]][e[1]] = Math.Min(cs[e[0]][e[1]], e[2]);
			if (!directed) cs[e[1]][e[0]] = Math.Min(cs[e[1]][e[0]], e[2]);
		}

		for (int k = 0; k < n; ++k)
			for (int i = 0; i < n; ++i)
				for (int j = 0; j < n; ++j)
				{
					if (cs[i][k] == long.MaxValue || cs[k][j] == long.MaxValue) continue;
					var nc = cs[i][k] + cs[k][j];
					if (cs[i][j] <= nc) continue;
					cs[i][j] = nc;
					inters[i][j] = k;
				}
		for (int i = 0; i < n; ++i) if (cs[i][i] < 0) return Tuple.Create<long[][], int[][]>(null, null);
		return Tuple.Create(cs, inters);
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード