結果
問題 |
No.2805 Go to School
|
ユーザー |
|
提出日時 | 2024-07-12 21:48:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 237 ms / 2,000 ms |
コード長 | 1,176 bytes |
コンパイル時間 | 3,328 ms |
コンパイル使用メモリ | 285,496 KB |
実行使用メモリ | 22,220 KB |
最終ジャッジ日時 | 2025-04-09 15:38:28 |
合計ジャッジ時間 | 7,772 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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(nullptr); ll N, M, L, S, E; cin >> N >> M >> L >> S >> E; vector<vector<pair<ll, ll>>> g(N); for(ll i = 0, u, v, w; i < M; i++) { cin >> u >> v >> w; u--, v--; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } vector<ll> T(L); for(auto &i : T) { cin >> i; i--; } auto Dijkstra = [&](ll s) { auto chmin = [&](auto &a, const auto &b) { return a > b ? (a = b, true) : false; }; vector<ll> d(N, 1e18); d[s] = 0; priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q; q.emplace(0, s); while(!q.empty()) { auto [tmp, v] = q.top(); q.pop(); if(tmp > d[v]) { continue; } for(auto &[nv, c] : g[v]) { if(chmin(d[nv], d[v] + c)) { q.emplace(d[nv], nv); } } } return d; }; vector<ll> d1 = Dijkstra(0), d2 = Dijkstra(N - 1); ll ans = 1e18; for(auto &i : T) { if(d1[i] >= S + E) { continue; } if(d1[i] < S) { d1[i] = S; } ans = min(ans, d1[i] + d2[i] + 1); } cout << (ans > 1e17 ? -1 : ans) << "\n"; }