結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2017-11-15 12:48:21 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 26 ms / 5,000 ms |
コード長 | 861 bytes |
コンパイル時間 | 2,058 ms |
コンパイル使用メモリ | 142,768 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 22:32:44 |
合計ジャッジ時間 | 3,505 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
void main(){ import std.stdio, std.string, std.conv, std.algorithm; int n, m, s, g; rd(n, m, s, g); auto d=new int[][](n, n); const inf=1_000_000_000; foreach(i; 0..n) fill(d[i], inf), d[i][i]=0; auto es=new int[][](n, n); foreach(i; 0..m){ int a, b, c; rd(a, b, c); d[a][b]=d[b][a]=c; es[a][b]=es[b][a]=c; } foreach(_; 0..n)foreach(i; 0..n)foreach(j; 0..n){ d[i][j]=min(d[i][j], d[i][_]+d[_][j]); } auto mn=d[s][g], r=new int[](0); for(auto cur=s; cur!=g; ){ r~=cur; foreach(nex; 0..n){ if(es[cur][nex] && d[cur][g]==d[nex][g]+es[cur][nex]){ cur=nex; break; } } } r~=g; writefln("%(%d %)", r); } void rd(T...)(ref T x){ import std.stdio, std.string, std.conv; auto l=readln.split; assert(l.length==x.length); foreach(i, ref e; x){ e=l[i].to!(typeof(e)); } }