結果
問題 |
No.2805 Go to School
|
ユーザー |
|
提出日時 | 2024-07-31 20:07:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,679 bytes |
コンパイル時間 | 1,744 ms |
コンパイル使用メモリ | 174,084 KB |
実行使用メモリ | 22,240 KB |
最終ジャッジ日時 | 2025-04-09 15:42:54 |
合計ジャッジ時間 | 8,894 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 WA * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (int)n; i++) #define INF 1e18 using ll = long long int; struct Edge { int to; int dist; Edge(int to, int dist) : to(to), dist(dist) {} bool operator=(const Edge &rhs) const { return to == rhs.to; } }; vector<ll> dijkstra(int N, int s, vector<vector<Edge>> &graph) { vector<ll> distance(N, INF); vector<int> from(N, -1); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q; distance[s] = 0; q.push({0, s}); while (!q.empty()) { pair<ll, int> p = q.top(); q.pop(); ll path_now = p.first; int p_now = p.second; if (distance[p_now] < path_now) continue; for (Edge e : graph[p_now]) { ll path_new = path_now + e.dist; int p_new = e.to; if (path_new < distance[p_new]) { distance[p_new] = path_new; from[p_new] = p_now; q.push({path_new, p_new}); } } } return distance; } int main() { int n, m, l, s, e; cin >> n >> m >> l >> s >> e; vector<vector<Edge>> g(n); rep(i, m) { int a, b, t; cin >> a >> b >> t; a--; b--; g[a].push_back(Edge(b, t)); g[b].push_back(Edge(a, t)); } vector<int> t(n, 0); rep(i, l) { int ti; cin >> ti; ti--; t[ti] = 1; } vector<ll> d = dijkstra(n, 0, g); vector<ll> r = dijkstra(n, n-1, g); ll ans = INF; rep(i, n) { if (t[i] == 0) continue; if (d[i] >= s && d[i] <= s + e) { ans = min(d[i] + 1 + r[i], ans); } if (d[i] < s) { ans = min(s + 1 + r[i], ans); } } if (ans == INF) cout << -1 << endl; else cout << ans << endl; return 0; }