結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
|
提出日時 | 2016-09-14 14:32:12 |
言語 | D (dmd 2.109.1) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,916 bytes |
コンパイル時間 | 969 ms |
コンパイル使用メモリ | 136,140 KB |
実行使用メモリ | 812,108 KB |
最終ジャッジ日時 | 2024-06-12 04:22:21 |
合計ジャッジ時間 | 6,819 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 3 MLE * 1 -- * 22 |
ソースコード
import std.algorithm, std.array, std.container, std.range, std.bitmanip; import std.numeric, std.math, std.bigint, std.random, core.bitop; import std.string, std.regex, std.conv, std.stdio, std.typecons; void main() { auto rd1 = readln.split.map!(to!size_t); auto n = rd1[0], m = rd1[1], s = rd1[2], t = rd1[3]; auto g = new Graph!int(n); foreach (_; 0..m) { auto rd2 = readln.split; auto a = rd2[0].to!size_t, b = rd2[1].to!size_t, c = rd2[2].to!int; g[a, b] = g[b, a] = c; } writeln(g.dijkstra(s, t).map!(to!string).join(" ")); } class Mat2(T) { size_t n; // size T[][] v; // values this(size_t n) { this.n = n; v = new T[][](n, n); } T opIndex(size_t i, size_t j) { return v[i][j]; } T opIndexAssign(T w, size_t i, size_t j) { v[i][j] = w; return w; } } class Mat2HasInf(T) : Mat2!T { T inf; // infinite this(size_t n, T inf = -1) { super(n); this.inf = inf; } bool isInf(size_t i, size_t j) { return v[i][j] == inf; } } class Graph(T) : Mat2HasInf!T { this(size_t n, T inf = -1) { super(n, inf); foreach (i; 0..n) v[i][] = inf; foreach (i; 0..n) v[i][i] = 0; } size_t[] dijkstra(size_t s, size_t g) { struct qitem { size_t v; T w; size_t[] r; int opCmp(qitem rhs) { if (w == rhs.w) return r == rhs.r ? 0 : (r < rhs.r ? -1 : 1); else return w < rhs.w ? -1 : 1; } } auto qi = heapify!("a > b")(Array!qitem()); auto visited = new bool[](n); void addNext(qitem q) { auto v = q.v, w = q.w, r = q.r; visited[v] = true; foreach (i; 0..n) if (!isInf(v, i) && !visited[i]) qi.insert(qitem(i, w + this[v, i], r ~ i)); } addNext(qitem(s, 0, [s])); while (!qi.empty) { auto q = qi.front; qi.removeFront; if (q.v == g) return q.r; addNext(q); } return []; } }