結果
問題 |
No.2805 Go to School
|
ユーザー |
|
提出日時 | 2024-07-29 10:49:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,768 bytes |
コンパイル時間 | 1,478 ms |
コンパイル使用メモリ | 125,136 KB |
最終ジャッジ日時 | 2025-02-23 19:23:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 22 WA * 13 |
ソースコード
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <map> #include <set> #include <utility> #include <queue> #include <stack> #include <cstring> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <iomanip> #include <cassert> #include <memory.h> #include <functional> #include <bitset> #include <unordered_map> #include <unordered_set> #include <climits> int main() { int n,m,l,s,e; std::cin >> n >> m >> l >> s >> e; using edge = std::pair<long long, int>; std::vector<std::vector<edge>> g(n); for (int i = 0; i < m; i++) { int u, v, w; std::cin >> u >> v >> w; u--,v--; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } auto dij = [&](int start) -> std::vector<long long> { std::vector<long long> dist(n, 1e18); dist[start] = 0; std::priority_queue<edge, std::vector<edge>, std::greater<edge>> pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (dist[u] != d) continue; for (auto [v, w] : g[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }; long long ans = 1e18; auto dist1 = dij(0); auto dist2 = dij(n - 1); for (int i = 0; i < l; i++) { int u; std::cin >> u; u--; if (dist1[u] <= s + e) { long long leave_time = dist1[u]; if (dist1[u] < s) leave_time = s; ans = std::min(ans, leave_time + 1 + dist2[u]); } } std::cout << ans << '\n'; }