結果
問題 | No.2805 Go to School |
ユーザー |
|
提出日時 | 2024-07-12 23:51:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,002 bytes |
コンパイル時間 | 2,273 ms |
コンパイル使用メモリ | 213,440 KB |
最終ジャッジ日時 | 2025-02-22 05:47:52 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 22 WA * 13 |
ソースコード
#include <bits/stdc++.h> using namespace std; class Dijkstra { int N; long long S; long long E; const vector<vector<pair<int, long long>>> &G; const vector<bool> &T; public: Dijkstra(int N, long long S, long long E, const vector<vector<pair<int, long long>>> &G, const vector<bool> &T) : N(N), S(S), E(E), G(G), T(T) { } long long dijkstra() { vector<vector<long long>> dist(N, vector<long long>(2, -(1LL << 62))); vector<vector<bool>> visited(N, vector<bool>(2, false)); queue<pair<long long, pair<int, bool>>> Q; dist[0][false] = 0LL; Q.push( { dist[0][false], { 0, false } }); while (!Q.empty()) { pair<long long, pair<int, bool>> q = Q.front(); Q.pop(); if (q.second.first == N - 1 && q.second.second) { return -dist[N - 1][true]; } if (visited[q.second.first][q.second.second]) continue; visited[q.second.first][q.second.second] = true; if (!q.second.second && -dist[q.second.first][q.second.second] >= S + E) continue; if (!q.second.second && T[q.second.first]) { long long d = min(-S - 1, q.first - 1); if (d > dist[q.second.first][true]) { dist[q.second.first][true] = d; Q.push( { d, { q.second.first, true } }); } } for (pair<int, long long> u : G[q.second.first]) { long long d = dist[q.second.first][q.second.second] - u.second; if (d > dist[u.first][q.second.second]) { dist[u.first][q.second.second] = d; Q.push( { d, { u.first, q.second.second } }); } } } return -1; } ~Dijkstra() { } }; int main() { int n, m, l; long long s, e; cin >> n >> m >> l >> s >> e; vector<vector<pair<int, long long>>> G(n); for (int i = 0; i < m; i++) { int a, b; long long t; cin >> a >> b >> t; a -= 1; b -= 1; G[a].push_back( { b, t }); G[b].push_back( { a, t }); } vector<bool> T(n, false); for (int i = 0; i < l; i++) { int t; cin >> t; T[--t] = true; } Dijkstra dijkstra(n, s, e, G, T); cout << dijkstra.dijkstra() << endl; return 0; }