結果
問題 | No.2805 Go to School |
ユーザー |
|
提出日時 | 2024-07-12 22:13:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,084 bytes |
コンパイル時間 | 2,205 ms |
コンパイル使用メモリ | 203,276 KB |
最終ジャッジ日時 | 2025-02-22 04:12:50 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 3 |
other | AC * 26 WA * 9 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; ll const inf = (ll)1e18; using P = pair<ll, int>; int main () { int N, M, L; ll S, E; cin >> N >> M >> L >> S >> E; std::vector<P> gr[200020]; while (M--) { int a, b; ll c; cin >> a >> b >> c; gr[--a].emplace_back(c, --b); gr[b].emplace_back(c, a); } vector<ll> D1(N, inf), D2(N, inf); D1[0] = D2[N - 1] = 0; priority_queue<P, vector<P>, greater<P>> pque; pque.emplace(0, 0); while (!pque.empty()) { auto [l, u] = pque.top(); pque.pop(); if (l != D1[u]) continue; for (auto [c, v] : gr[u]) { if (D1[v] > l + c) { D1[v] = l + c; pque.emplace(l + c, v); } } } pque.emplace(0, N - 1); while (!pque.empty()) { auto [l, u] = pque.top(); pque.pop(); if (l != D2[u]) continue; for (auto [c, v] : gr[u]) { if (D2[v] > l + c) { D2[v] = l + c; pque.emplace(l + c, v); } } } ll ans = inf * 3; while (L--) { int t; cin >> t; t --; if (D1[t] < E) { ans = min(ans, max(D1[t], S) + 1 + D2[t]); } } cout << (ans >= inf ? -1ll : ans) << endl; }