結果
問題 |
No.2805 Go to School
|
ユーザー |
![]() |
提出日時 | 2024-07-14 21:11:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 280 ms / 2,000 ms |
コード長 | 2,036 bytes |
コンパイル時間 | 6,269 ms |
コンパイル使用メモリ | 333,020 KB |
実行使用メモリ | 19,820 KB |
最終ジャッジ日時 | 2025-04-09 15:42:18 |
合計ジャッジ時間 | 11,817 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> #include <cassert> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; //using mint = modint1000000007; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repu(i, s, t) for (int i = (int)(s); i < (int)(t); i++) #define repd(i, s, t) for (int i = (int)(s)-1; i >= (int)(t); i--) #define all(v) v.begin(), v.end() template<typename T> bool chmax(T &a, const T b) { if(a >= b) return false; a = b; return true; } template<typename T> bool chmin(T &a, const T b) { if(a <= b) return false; a = b; return true; } template<typename T> istream& operator>>(istream &in, vector<T> &a) { for(T &x: a) in >> x; return in; } template<typename T> ostream& operator<<(ostream &out, const vector<T> &a) { for(const T &x: a) out << x << ' '; return out; } const int di[] = {1, 0, -1, 0, 1, 1, -1, -1, 0}; const int dj[] = {0, 1, 0, -1, -1, 1, 1, -1, 0}; int main() { int n, m, l, s, e; cin >> n >> m >> l >> s >> e; vector<vector<pair<int, int>>> g(n); rep(i, m) { int a, b, t; cin >> a >> b >> t; a--, b--; g[a].emplace_back(b, t); g[b].emplace_back(a, t); } vector<int> ts(l); cin >> ts; rep(i, l) ts[i]--; using P = pair<ll, int>; priority_queue<P, vector<P>, greater<P>> pq; auto dij = [&](vector<ll> &dist) { while(!pq.empty()) { auto [d, pos] = pq.top(); pq.pop(); if(dist[pos] < d) continue; for(auto[to, c]: g[pos]) { if(chmin(dist[to], dist[pos] + c)) { pq.emplace(dist[to], to); } } } }; const ll INF = 1e18; vector<ll> d1(n, INF); d1[0] = 0; pq.emplace(0, 0); dij(d1); vector<ll> d2(n, INF); for(int x: ts) { if(d1[x] >= s+e) continue; d2[x] = max(ll(s), d1[x]) + 1; pq.emplace(d2[x], x); } dij(d2); cout << (d2[n-1] < INF ? d2[n-1] : -1) << endl; return 0; }