結果
問題 |
No.2805 Go to School
|
ユーザー |
|
提出日時 | 2024-07-19 05:37:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 1,293 bytes |
コンパイル時間 | 2,090 ms |
コンパイル使用メモリ | 212,812 KB |
実行使用メモリ | 22,216 KB |
最終ジャッジ日時 | 2025-04-09 15:42:40 |
合計ジャッジ時間 | 5,845 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m, l, s, e; cin >> n >> m >> l >> s >> e; vector<vector<pair<int,int>>> g(n); vector<bool> toilet(n); vector<vector<ll>> dp(2, vector<ll>(n, 1ll << 61)); priority_queue<tuple<ll,int,int>, vector<tuple<ll,int,int>>, greater<tuple<ll,int,int>>> pq; for(int i = 0; i < m; i++){ int u, v, c; cin >> u >> v >> c; u--, v--; g[u].emplace_back(v, c); g[v].emplace_back(u, c); } for(int i = 0; i < l; i++){ int v; cin >> v; toilet[--v] = true; } dp[0][0] = 0; pq.emplace(0, 0, 0); while(!pq.empty()){ auto [d, st, v] = pq.top(); pq.pop(); if(d > dp[st][v]) continue; if(st == 0 && toilet[v] && d < s + e){ ll t = max((ll)s, d) + 1; if(t < dp[1][v]){ dp[1][v] = t; pq.emplace(t, 1, v); } } for(auto [u, c] : g[v]){ if(d + c >= dp[st][u]) continue; dp[st][u] = d + c; pq.emplace(dp[st][u], st, u); } } ll ans = dp[1][n - 1]; if(ans >> 61 & 1) ans = -1; cout << ans << '\n'; }