結果
問題 |
No.2805 Go to School
|
ユーザー |
|
提出日時 | 2024-07-12 21:33:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 321 ms / 2,000 ms |
コード長 | 1,146 bytes |
コンパイル時間 | 1,649 ms |
コンパイル使用メモリ | 171,652 KB |
実行使用メモリ | 22,836 KB |
最終ジャッジ日時 | 2025-04-09 15:37:22 |
合計ジャッジ時間 | 8,006 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int n,m,c,s,t; cin >> n >> m >> c >> s >> t; vector<vector<pair<int,int>>> a(n); while(m--) { int x,y,w; cin >> x >> y >> w; x--,y--; a[x].push_back({y,w}); a[y].push_back({x,w}); } vector<int> v(n,1e18),w(n,1e18); priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; v[0] = 0; w[n-1] = 0; q.push({0,0}); while(q.size() > 0) { int x,e; tie(e,x) = q.top(); q.pop(); if(v[x] != e) continue; int l = a[x].size(); for(int i = 0; i < l; i++) { int y,f; tie(y,f) = a[x][i]; if(v[y] > v[x]+f) { v[y] = v[x]+f; q.push({v[y],y}); } } } q.push({0,n-1}); while(q.size() > 0) { int x,e; tie(e,x) = q.top(); q.pop(); if(w[x] != e) continue; int l = a[x].size(); for(int i = 0; i < l; i++) { int y,f; tie(y,f) = a[x][i]; if(w[y] > w[x]+f) { w[y] = w[x]+f; q.push({w[y],y}); } } } int ans = 1e18; while(c--) { int x; cin >> x; x--; if(v[x] < s+t) ans = min(ans,max(s,v[x])+1+w[x]); } if(ans >= 1e16) cout << -1 << endl; else cout << ans << endl; }