結果
| 問題 | No.2805 Go to School |
| ユーザー |
 tobbie
|
| 提出日時 | 2024-07-27 20:40:39 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,735 bytes |
| コンパイル時間 | 2,319 ms |
| コンパイル使用メモリ | 179,540 KB |
| 実行使用メモリ | 16,060 KB |
| 最終ジャッジ日時 | 2024-07-27 20:40:50 |
| 合計ジャッジ時間 | 10,379 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
13,884 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,944 KB |
| testcase_04 | AC | 174 ms
12,736 KB |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define INF 1e9
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<int> dijkstra(int N, int s, vector<vector<Edge>> &graph) {
vector<int> distance(N, INF);
vector<int> from(N, -1);
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> q;
distance[s] = 0;
q.push({0, s});
while (!q.empty()) {
pair<int, int> p = q.top();
q.pop();
int path_now = p.first;
int p_now = p.second;
if (distance[p_now] < path_now)
continue;
for (Edge e : graph[p_now]) {
int 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<int> d = dijkstra(n, 0, g);
int ans = INF;
if (d[n-1] < s)
ans = s + 1;
else if (d[n-1] <= s + e)
ans = d[n-1] + 1;
rep(i, n) {
if (t[i] == 1) {
vector<int> ret = dijkstra(n, i, g);
if (d[i] < s)
ans = min(s + 1 + ret[n-1], ans);
else if (d[i] >= s && d[i] <= s + e)
ans = min(d[i] + 1 + ret[n-1], ans);
}
}
if (ans == 1e9)
cout << -1 << endl;
else
cout << ans << endl;
return 0;
}