結果
問題 | No.1344 Typical Shortest Path Sum |
ユーザー | kakel-san |
提出日時 | 2024-08-11 23:49:58 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 1,368 bytes |
コンパイル時間 | 7,166 ms |
コンパイル使用メモリ | 172,632 KB |
実行使用メモリ | 190,140 KB |
最終ジャッジ日時 | 2024-08-11 23:50:22 |
合計ジャッジ時間 | 13,914 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (88 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static long[] NList => ReadLine().Split().Select(long.Parse).ToArray(); static long[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, m) = ((int)c[0], (int)c[1]); var map = NArr(m); WriteLine(string.Join("\n", Path(n, m, map))); } static long[] Path(int n, int m, long[][] map) { var INF = long.MaxValue / 3; var wf = new long[n][]; for (var i = 0; i < n; ++i) { wf[i] = Enumerable.Repeat(INF, n).ToArray(); wf[i][i] = 0; } foreach (var edge in map) { wf[edge[0] - 1][edge[1] - 1] = Math.Min(wf[edge[0] - 1][edge[1] - 1], edge[2]); } for (var k = 0; k < n; ++k) for (var i = 0; i < n; ++i) for (var j = 0; j < n; ++j) { wf[i][j] = Math.Min(wf[i][j], wf[i][k] + wf[k][j]); } var ans = new long[n]; for (var i = 0; i < n; ++i) for (var j = 0; j < n; ++j) if (wf[i][j] < INF / 2) ans[i] += wf[i][j]; return ans; } }