結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー | chaemon |
提出日時 | 2019-07-23 00:25:24 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 4,192 bytes |
コンパイル時間 | 3,266 ms |
コンパイル使用メモリ | 70,596 KB |
実行使用メモリ | 7,960 KB |
最終ジャッジ日時 | 2023-09-14 23:42:01 |
合計ジャッジ時間 | 4,514 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,384 KB |
testcase_04 | AC | 5 ms
4,376 KB |
testcase_05 | AC | 8 ms
6,248 KB |
testcase_06 | AC | 11 ms
6,484 KB |
testcase_07 | AC | 3 ms
4,376 KB |
testcase_08 | AC | 3 ms
4,380 KB |
testcase_09 | AC | 3 ms
4,380 KB |
testcase_10 | AC | 3 ms
4,376 KB |
testcase_11 | AC | 3 ms
4,376 KB |
testcase_12 | AC | 3 ms
4,380 KB |
testcase_13 | AC | 3 ms
4,376 KB |
testcase_14 | AC | 3 ms
4,376 KB |
testcase_15 | AC | 3 ms
4,376 KB |
testcase_16 | AC | 3 ms
4,376 KB |
testcase_17 | AC | 3 ms
4,376 KB |
testcase_18 | AC | 3 ms
4,380 KB |
testcase_19 | AC | 3 ms
4,380 KB |
testcase_20 | AC | 3 ms
4,380 KB |
testcase_21 | AC | 3 ms
4,380 KB |
testcase_22 | AC | 3 ms
4,376 KB |
testcase_23 | AC | 3 ms
4,376 KB |
testcase_24 | AC | 4 ms
4,376 KB |
testcase_25 | AC | 3 ms
4,376 KB |
testcase_26 | AC | 3 ms
4,376 KB |
testcase_27 | AC | 2 ms
4,376 KB |
testcase_28 | AC | 13 ms
7,960 KB |
testcase_29 | AC | 2 ms
4,380 KB |
コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 37) Warning: imported and not used: 'macros' [UnusedImport] /home/judge/data/code/Main.nim(2, 45) Warning: imported and not used: 'math' [UnusedImport] /home/judge/data/code/Main.nim(2, 29) Warning: imported and not used: 'tables' [UnusedImport]
ソースコード
#{{{ header import algorithm, sequtils, tables, macros, math, sets, strutils when defined(MYDEBUG): import header proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.} proc getchar(): char {.header: "<stdio.h>", varargs.} proc nextInt(): int = scanf("%lld",addr result) proc nextFloat(): float = scanf("%lf",addr result) proc nextString(): string = var get = false result = "" while true: var c = getchar() if int(c) > int(' '): get = true result.add(c) else: if get: break get = false template `max=`*(x,y:typed):void = x = max(x,y) template `min=`*(x,y:typed):void = x = min(x,y) template infty(T): untyped = ((T(1) shl T(sizeof(T)*8-2)) - 1) #}}} #{{{ Graph type Edge = object src,dst:int weight:int rev:int proc newEdge(src,dst:int,weight:int = 1,rev:int = -1):Edge = var e:Edge e.src = src e.dst = dst e.weight = weight e.rev = rev return e proc `<`(l,r:Edge):bool = return l.weight < r.weight type Graph = seq[seq[Edge]] proc newGraph(n:int):Graph= var g:Graph g = newSeqWith(n,newSeq[Edge]()) return g proc addBiEdge(g:var Graph,src,dst:int,weight:int=1):void = g[src].add(newEdge(src,dst,weight,g[dst].len)) g[dst].add(newEdge(dst,src,weight,g[src].len-1)) proc addEdge(g:var Graph,src,dst:int,weight:int=1):void = g[src].add(newEdge(src,dst,weight,-1)) #}}} proc cmp2(l,r:Edge):int = if l.dst < r.dst : -1 else: 1 import heapqueue proc shortest_path(g:Graph, s:int): (seq[int],seq[int]) = var n = g.len dist = newSeqWith(n,int.infty) prev = newSeqWith(n,-1) Q = initHeapQueue[Edge]() dist[s] = 0 Q.push(newEdge(-2,s,0)) while Q.len > 0: var e = Q.pop() if prev[e.dst] != -1: continue prev[e.dst] = e.src; for f in g[e.dst]: var w = e.weight + f.weight; if dist[f.dst] > w: dist[f.dst] = w; Q.push(newEdge(f.src, f.dst, w)); discard return (dist,prev) #//{{{ shortest_path(graph g, int s) : Dijkstra #template<class Weight> # const graph<Weight> &g; # const int &s; # vector<Weight> dist; # vector<int> prev; #// dijkstra_t(const graph<Weight> &g,int s):g(g),s(s),dist(g.size(),g.inf),prev(g.size(),-1){} # dijkstra_t(const graph<Weight> &g,const int &s):g(g),s(s),dist(g.size(),g.inf),prev(g.size(),-1){ # /* # assert(dist.size()==g.size()); # REP(i,dist.size())assert(dist[i]>=0 and dist[i]+dist[i]>=0); # */ # } # vector<int> path(int t) { # vector<int> path; # for (int u = t; u >= 0; u = prev[u])path.push_back(u); # reverse(ALL(path)); # return path; # } # void dijkstra(){ # dist[s] = 0; # priority_queue<edge<Weight> > Q; // "e < f" <=> "e.weight > f.weight" # for (Q.push(edge<Weight>(-2, s, 0)); !Q.empty(); ) { # edge<Weight> e = Q.top(); Q.pop(); # if (prev[e.dst] != -1) continue; # prev[e.dst] = e.src; # for(auto f:g[e.dst]) { #// assert(e.weight<=g.inf); #// assert(0<=f.weight and f.weight<=g.inf); # Weight w = e.weight + f.weight; # if (dist[f.dst] > w) { # dist[f.dst] = w; # Q.push(edge<Weight>(f.src, f.dst, w)); # } # } # } # } # /* # void count_dp(){ # vector<pair<Weight,int> > d; # REP(u,g.size())d.push_back({dist[u],u}); # sort(ALL(d)); # dp.assign(g.size(),mod_int()); # dp[s] = 1; # REP(i,d.size()){ # int u = d[i].second; # for(auto &&e:g[u]){ # if(dist[e.dst]+e.weight==dist[u]){ # dp[u]+=dp[e.dst]; # } # } # } # } # */ #}; #template<class Weight> #dijkstra_t<Weight> shortest_path(const graph<Weight> &g, int s) { # dijkstra_t<Weight> ret(g,s); # ret.dijkstra(); #// ret.count_dp(); # return ret; #} #//}}} proc main():void = var N = nextInt() M = nextInt() S = nextInt() G = nextInt() a = newSeq[int](M) b = newSeq[int](M) c = newSeq[int](M) g = newGraph(N) for i in 0..M-1: a[i] = nextInt();b[i] = nextInt();c[i] = nextInt() g.addBiEdge(a[i],b[i],c[i]) for u in 0..N-1: g[u].sort(cmp2) var (dist,_) = shortest_path(g,G) var cur = S ans = newSeq[int]() while cur != G: ans.add(cur) for e in g[cur]: if dist[cur] == dist[e.dst] + e.weight: cur = e.dst break ans.add(cur) echo ans.join(" ") discard main()