結果
問題 |
No.2805 Go to School
|
ユーザー |
|
提出日時 | 2024-07-09 21:06:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 312 ms / 2,000 ms |
コード長 | 1,531 bytes |
コンパイル時間 | 2,340 ms |
コンパイル使用メモリ | 210,040 KB |
実行使用メモリ | 24,772 KB |
最終ジャッジ日時 | 2025-04-09 15:36:02 |
合計ジャッジ時間 | 8,760 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using ll = long long; const ll mod = 998244353; #define fi first #define se second #define rep(i,n) for(ll i=0;i<n;i++) #define all(x) x.begin(),x.end() #define faster ios::sync_with_stdio(false);cin.tie(nullptr) using P = pair<ll,ll>; struct Edge{ ll to; ll cost; }; using Graph = vector<vector<Edge>>; const ll INF = 1LL<<60; void dijkstra(const Graph &G,ll s,vector<ll> &dis){ ll N=G.size(); dis.assign(N,INF); priority_queue<P,vector<P>,greater<P>> pq; dis[s]=0; pq.emplace(dis[s],s); while(!pq.empty()){ P p=pq.top(); pq.pop(); ll v=p.se; if(p.fi>dis[v]) continue; for(auto &e:G[v]){ if(dis[e.to]>dis[v]+e.cost){ dis[e.to]=dis[v]+e.cost; pq.emplace(dis[e.to],e.to); } } } } int main() { ll N,M,L,S,E; cin >> N >> M >> L >> S >> E; ll ans=INF; Graph G(N); rep(i,M){ ll a,b,t; cin >> a >> b >> t; G[a-1].push_back({b-1,t}); G[b-1].push_back({a-1,t}); } vector<ll> dis1,dis2; dijkstra(G,0,dis1); dijkstra(G,N-1,dis2); rep(i,L){ ll t; cin >> t; t--; if(dis1[t]<=S+E-1){ ans=min(ans,max(S,dis1[t])+1+dis2[t]); } } if(ans==INF){ cout << -1 << endl; }else{ cout << ans << endl; } return 0; }