結果
問題 | 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;}