結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
|
提出日時 | 2015-03-01 23:54:32 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 237 ms / 5,000 ms |
コード長 | 748 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 77,192 KB |
実行使用メモリ | 80,284 KB |
最終ジャッジ日時 | 2024-06-24 00:42:46 |
合計ジャッジ時間 | 7,184 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
import copy inf = 10**9 def dfs(path,t): if path[-1] == G: return path spath = set(path) res = [] for i in xrange(N): if i not in spath and t+cost[path[-1]][i]+mincost[i][G] <= time: res = dfs(path+[i],t+cost[path[-1]][i]) if res: return res return [] N,M,S,G = map(int,raw_input().split()) cost = [[inf]*N for i in xrange(N)] for i in xrange(N): cost[i][i] = 0 for loop in xrange(M): a,b,c = map(int,raw_input().split()) cost[a][b] = cost[b][a] = c mincost = copy.deepcopy(cost) for k in xrange(N): for i in xrange(N): for j in xrange(N): mincost[i][j] = min(mincost[i][j], mincost[i][k]+mincost[k][j]) time = mincost[S][G] print " ".join(map(str,dfs([S],0)))