結果
問題 |
No.2805 Go to School
|
ユーザー |
![]() |
提出日時 | 2024-07-04 22:35:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 1,382 bytes |
コンパイル時間 | 2,283 ms |
コンパイル使用メモリ | 209,092 KB |
実行使用メモリ | 22,396 KB |
最終ジャッジ日時 | 2025-04-09 15:36:00 |
合計ジャッジ時間 | 9,399 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int N,M,L,S,E; cin>>N>>M>>L>>S>>E; vector<vector<pair<int,int>>> G(N); for(int i=0;i<M;i++){ int a,b,c; cin>>a>>b>>c; a--; b--; G[a].push_back({b,c}); G[b].push_back({a,c}); } set<int> T; for(int i=0;i<L;i++){ int a; cin>>a; T.insert(a-1); } vector<int> dist(N,1e18); dist[0] = 0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; pq.push({0,0}); while(!pq.empty()){ int u,w; tie(w,u) = pq.top(); pq.pop(); if(dist[u] != w) continue; for(auto [v,x]:G[u])if(dist[v] > w+x){ dist[v] = w+x; pq.push({dist[v],v}); } } for(int i=0;i<N;i++){ dist[i] = max(dist[i],S); if(S <= dist[i] && dist[i] < S+E && T.count(i)){ dist[i]++; pq.push({dist[i],i}); } else{ dist[i] = 1e18; } } //cout<<dist[N-1]<<endl; if(dist[N-1] > S+E) dist[N-1] = 1e18; else{ cout<<dist[N-1]<<endl; return 0; } while(!pq.empty()){ int u,w; tie(w,u) = pq.top(); pq.pop(); if(dist[u] != w) continue; for(auto [v,x]:G[u])if(dist[v] > w+x){ dist[v] = w+x; pq.push({dist[v],v}); } } cout<<(dist[N-1]+1 > 1e17 ? -1 : dist[N-1])<<endl; }