結果
問題 | No.2805 Go to School |
ユーザー | sibasyun |
提出日時 | 2024-07-12 21:36:16 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 440 ms / 2,000 ms |
コード長 | 3,942 bytes |
コンパイル時間 | 4,669 ms |
コンパイル使用メモリ | 280,356 KB |
実行使用メモリ | 42,360 KB |
最終ジャッジ日時 | 2024-07-16 01:38:31 |
合計ジャッジ時間 | 11,754 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 189 ms
28,112 KB |
testcase_05 | AC | 218 ms
16,016 KB |
testcase_06 | AC | 122 ms
11,892 KB |
testcase_07 | AC | 112 ms
10,240 KB |
testcase_08 | AC | 193 ms
15,232 KB |
testcase_09 | AC | 120 ms
11,136 KB |
testcase_10 | AC | 112 ms
9,600 KB |
testcase_11 | AC | 388 ms
39,308 KB |
testcase_12 | AC | 223 ms
22,448 KB |
testcase_13 | AC | 332 ms
28,500 KB |
testcase_14 | AC | 47 ms
9,856 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 1 ms
6,940 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 164 ms
14,928 KB |
testcase_19 | AC | 117 ms
12,800 KB |
testcase_20 | AC | 263 ms
20,584 KB |
testcase_21 | AC | 440 ms
42,360 KB |
testcase_22 | AC | 174 ms
19,584 KB |
testcase_23 | AC | 249 ms
22,352 KB |
testcase_24 | AC | 248 ms
21,332 KB |
testcase_25 | AC | 77 ms
13,496 KB |
testcase_26 | AC | 336 ms
39,112 KB |
testcase_27 | AC | 194 ms
37,864 KB |
testcase_28 | AC | 25 ms
16,236 KB |
testcase_29 | AC | 38 ms
17,940 KB |
testcase_30 | AC | 105 ms
28,876 KB |
testcase_31 | AC | 167 ms
16,932 KB |
testcase_32 | AC | 249 ms
31,584 KB |
testcase_33 | AC | 333 ms
34,020 KB |
testcase_34 | AC | 2 ms
6,944 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 124 ms
14,848 KB |
testcase_37 | AC | 138 ms
19,456 KB |
testcase_38 | AC | 251 ms
31,880 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #include <algorithm> #include <iostream> #include <iomanip> #include <math.h> #include <random> #include <chrono> #include <cstdint> using namespace std; using namespace atcoder; // using mint = modint998244353; using mint = modint1000000007; using vi = vector<int>; using vvi = vector<vector<int>>; using vl = vector<long long>; using vvl = vector<vector<long long>>; using ll = long long; template <class T> using max_heap = priority_queue<T>; template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, f, n) for (int i = (int) f; i < (int)(n); i++) #define repd(i, n, l) for (int i = (int) n; i >= (int) l; i--) #define all(p) p.begin(),p.end() vector<pair<int, int>> dydx{{-1, 0}, {1, 0}, {0, -1 }, {0, 1}}; const ll inf = 1LL << 60; void print(){ putchar(' '); } void print(bool a){ printf("%d", a); } void print(int a){ printf("%d", a); } void print(unsigned a){ printf("%u", a); } void print(long a){ printf("%ld", a); } void print(long long a){ printf("%lld", a); } void print(unsigned long long a){ printf("%llu", a); } void print(char a){ printf("%c", a); } void print(char a[]){ printf("%s", a); } void print(const char a[]){ printf("%s", a); } void print(float a){ printf("%.15f", a); } void print(double a){ printf("%.15f", a); } void print(long double a){ printf("%.15Lf", a); } void print(const string& a){ for(auto&& i : a) print(i); } template<class T> void print(const complex<T>& a){ if(a.real() >= 0) print('+'); print(a.real()); if(a.imag() >= 0) print('+'); print(a.imag()); print('i'); } template<class T> void print(const vector<T>&); template<class T, size_t size> void print(const array<T, size>&); template<class T, class L> void print(const pair<T, L>& p); template<class T, size_t size> void print(const T (&)[size]); template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } } template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } } template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } } template<class T, class L> void print(const pair<T, L>& p){ print(p.first); putchar(' '); print(p.second); } template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } } template<class T> void print(const T& a){ cout << a; } int main() { int n, m, l; ll s, e; cin >> n >> m >> l >> s >> e; vvl dist(n, vl(2, inf)); dist[0][0] = 0; vector<vector<pair<int, ll>>> G(n); vector<vector<bool>> seen(n, vector<bool>(2, false)); rep(i, m){ int a, b; ll t; cin >> a >> b >> t; a--, b--; G[a].push_back({b, t}); G[b].push_back({a, t}); } vector<int> T(n, 0); rep(i, l){ int tt; cin >> tt; tt--; T[tt] = 1; } min_heap<tuple<ll, int, int>> hq; hq.push({0, 0, 0}); while (!hq.empty()){ int now = get<1>(hq.top()); int f = get<2>(hq.top());hq.pop(); if (seen[now][f]) continue; seen[now][f] = true; if (!f && T[now] && dist[now][0] <= s+e){ if (dist[now][1] > dist[now][0] + 1){ dist[now][1] = max(dist[now][0] + 1, s+1); hq.push({dist[now][1], now, 1}); } } for (auto [nxt, nc] : G[now]){ if (dist[nxt][f] > dist[now][f] + nc && !seen[nxt][f]){ dist[nxt][f] = dist[now][f] + nc; hq.push({dist[nxt][f], nxt, f}); } } } if (dist[n-1][1] == inf) cout << -1 << endl; else cout << dist[n-1][1] << endl; return 0; }