結果
問題 |
No.92 逃走経路
|
ユーザー |
|
提出日時 | 2025-07-24 19:15:51 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 929 bytes |
コンパイル時間 | 5,221 ms |
コンパイル使用メモリ | 207,472 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-07-24 19:15:58 |
合計ジャッジ時間 | 6,665 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
module main; // https://kmjp.hatenablog.jp/entry/2014/12/08/0930 より // 重み付きグラフ import std; struct Edge { int to; long cost; } void main() { // 入力 int N, M, K; readln.chomp.formattedRead("%d %d %d", N, M, K); auto E = new Edge[][](N); foreach (_; 0 .. M) { int a, b; long c; readln.chomp.formattedRead("%d %d %d", a, b, c); --a, --b; E[a] ~= Edge(b, c); E[b] ~= Edge(a, c); } auto D = readln.split.to!(long[]); // 答えの計算 auto visited = new bool[][](2, N); visited[0][] = true; foreach (i; 0 .. K) { int cur = i % 2, tar = cur ^ 1; visited[tar][] = false; foreach (x; 0 .. N) { if (!visited[cur][x]) continue; foreach (y; 0 .. E[x].length) if (E[x][y].cost == D[i]) visited[tar][E[x][y].to] = true; } } int[] ans; foreach (i; 0 .. N) if (visited[K % 2][i]) ans ~= i + 1; // 答えの出力 writeln(ans.length); writefln("%(%d %)", ans); }