結果
問題 | No.614 壊れたキャンパス |
ユーザー | fura |
提出日時 | 2020-06-12 11:11:12 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 813 ms / 2,000 ms |
コード長 | 1,688 bytes |
コンパイル時間 | 2,574 ms |
コンパイル使用メモリ | 221,504 KB |
実行使用メモリ | 72,592 KB |
最終ジャッジ日時 | 2023-09-06 08:59:38 |
合計ジャッジ時間 | 11,814 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,384 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 731 ms
71,384 KB |
testcase_09 | AC | 766 ms
69,880 KB |
testcase_10 | AC | 635 ms
68,276 KB |
testcase_11 | AC | 801 ms
71,308 KB |
testcase_12 | AC | 813 ms
72,592 KB |
testcase_13 | AC | 797 ms
71,536 KB |
testcase_14 | AC | 741 ms
71,448 KB |
testcase_15 | AC | 605 ms
68,024 KB |
testcase_16 | AC | 717 ms
68,888 KB |
testcase_17 | AC | 355 ms
57,352 KB |
testcase_18 | AC | 355 ms
56,684 KB |
testcase_19 | AC | 366 ms
58,928 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; using lint=long long; template<class T> struct edge{ int to; T wt; edge(int to,const T& wt):to(to),wt(wt){} }; template<class T> using weighted_graph=vector<vector<edge<T>>>; template<class T> void add_undirected_edge(weighted_graph<T>& G,int u,int v,const T& wt){ G[u].emplace_back(v,wt); G[v].emplace_back(u,wt); } template<class T> void add_directed_edge(weighted_graph<T>& G,int u,int v,const T& wt){ G[u].emplace_back(v,wt); } template<class T> vector<T> Dijkstra(const weighted_graph<T>& G,int s){ constexpr T INF=numeric_limits<T>::max(); int n=G.size(); vector<T> d(n,INF); d[s]=0; priority_queue<pair<T,int>> Q; Q.emplace(0,s); while(!Q.empty()){ T d0=-Q.top().first; int u=Q.top().second; Q.pop(); if(d0>d[u]) continue; for(const auto& e:G[u]){ int v=e.to; if(d[v]>d[u]+e.wt) d[v]=d[u]+e.wt, Q.emplace(-d[v],v); } } return d; } int main(){ int n,m,s,t; scanf("%d%d%*d%d%d",&n,&m,&s,&t); s--; t--; map<pair<int,int>,int> f; f[{0,s}]=0; f[{n-1,t}]=1; weighted_graph<lint> G(2); rep(i,m){ int a,b,c; scanf("%d%d%d",&a,&b,&c); a--; b--; c--; if(f.count({a,b})==0) f[{a,b}]=f.size(); if(f.count({a+1,c})==0) f[{a+1,c}]=f.size(); int u=f[{a,b}],v=f[{a+1,c}]; G.resize(f.size()); add_directed_edge(G,u,v,0LL); } for(auto it=f.begin();it!=f.end();++it){ auto jt=it; ++jt; if(jt==f.end()) continue; auto [a1,b1]=it->first; auto [a2,b2]=jt->first; if(a1==a2){ add_undirected_edge(G,it->second,jt->second,lint(abs(b1-b2))); } } lint ans=Dijkstra(G,f[{0,s}])[f[{n-1,t}]]; printf("%lld\n",ans<LLONG_MAX?ans:-1); return 0; }