結果
問題 | No.2805 Go to School |
ユーザー | umimel |
提出日時 | 2024-07-12 21:41:10 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 308 ms / 2,000 ms |
コード長 | 3,829 bytes |
コンパイル時間 | 1,748 ms |
コンパイル使用メモリ | 182,004 KB |
実行使用メモリ | 37,736 KB |
最終ジャッジ日時 | 2024-07-16 01:38:32 |
合計ジャッジ時間 | 7,026 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 113 ms
33,604 KB |
testcase_05 | AC | 116 ms
26,692 KB |
testcase_06 | AC | 67 ms
15,308 KB |
testcase_07 | AC | 57 ms
15,648 KB |
testcase_08 | AC | 95 ms
27,216 KB |
testcase_09 | AC | 66 ms
15,596 KB |
testcase_10 | AC | 58 ms
16,620 KB |
testcase_11 | AC | 308 ms
37,736 KB |
testcase_12 | AC | 163 ms
25,376 KB |
testcase_13 | AC | 242 ms
33,624 KB |
testcase_14 | AC | 31 ms
8,804 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 94 ms
19,460 KB |
testcase_19 | AC | 65 ms
14,032 KB |
testcase_20 | AC | 160 ms
28,088 KB |
testcase_21 | AC | 272 ms
36,020 KB |
testcase_22 | AC | 100 ms
18,016 KB |
testcase_23 | AC | 148 ms
25,020 KB |
testcase_24 | AC | 146 ms
25,104 KB |
testcase_25 | AC | 42 ms
12,244 KB |
testcase_26 | AC | 178 ms
34,988 KB |
testcase_27 | AC | 135 ms
28,012 KB |
testcase_28 | AC | 13 ms
9,140 KB |
testcase_29 | AC | 19 ms
10,732 KB |
testcase_30 | AC | 67 ms
19,480 KB |
testcase_31 | AC | 80 ms
16,896 KB |
testcase_32 | AC | 135 ms
35,280 KB |
testcase_33 | AC | 206 ms
36,232 KB |
testcase_34 | AC | 2 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 76 ms
14,800 KB |
testcase_37 | AC | 92 ms
17,196 KB |
testcase_38 | AC | 183 ms
28,008 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i) #define rep(i, n) drep(i, 0, n - 1) #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); const ll MOD1000000007 = 1000000007; const ll MOD998244353 = 998244353; const ll MOD[3] = {999727999, 1070777777, 1000000007}; const ll LINF = 1LL << 60LL; const int IINF = (1 << 30) - 1; template<typename T> struct edge{ int from; int to; T cost; int id; edge(){} edge(int to, T cost=1) : from(-1), to(to), cost(cost){} edge(int to, T cost, int id) : from(-1), to(to), cost(cost), id(id){} edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){} void reverse(){swap(from, to);} }; template<typename T> struct edges : std::vector<edge<T>>{ void sort(){ std::sort( (*this).begin(), (*this).end(), [](const edge<T>& a, const edge<T>& b){ return a.cost < b.cost; } ); } }; template<typename T> struct graph : std::vector<edges<T>>{ int n = 0; int m = 0; edges<T> es; bool directed; graph(int n, bool directed) : n(n), directed(directed){ (*this).resize(n); } void add_edge(int from, int to, T cost=1){ if(directed){ es.push_back(edge<T>(from, to, cost, m)); (*this)[from].push_back(edge<T>(from, to, cost, m++)); }else{ if(from > to) swap(from, to); es.push_back(edge<T>(from, to, cost, m)); (*this)[from].push_back(edge<T>(from, to, cost, m)); (*this)[to].push_back(edge<T>(to, from, cost, m++)); } } }; template<typename T> struct redge{ int from, to; T cap, cost; int rev; redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){} redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){} }; template<typename T> using Edges = vector<edge<T>>; template<typename T> using weighted_graph = vector<Edges<T>>; template<typename T> using tree = vector<Edges<T>>; using unweighted_graph = vector<vector<int>>; template<typename T> using residual_graph = vector<vector<redge<T>>>; vector<long long> dijkstra(weighted_graph<long long> G, int src){ int n = (int)G.size(); vector<long long> dist(n, LINF); dist[src] = 0; priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> PQ; PQ.push({0, src}); while(!PQ.empty()){ int v = PQ.top().second; long long tmp = PQ.top().first; PQ.pop(); if(dist[v] < tmp) continue; for(edge<long long> e : G[v]){ if(dist[v]+e.cost < dist[e.to]){ dist[e.to] = dist[v]+e.cost; PQ.push({dist[e.to], e.to}); } } } return dist; } void solve(){ int N, M, L; ll S, E; cin >> N >> M >> L >> S >> E; weighted_graph<ll> G(N); for(int i=0; i<M; i++){ int u, v; ll w; cin >> u >> v >> w; u--; v--; G[u].pb(edge<ll>(v, w)); G[v].pb(edge<ll>(u, w)); } vector<int> T(L); for(int i=0; i<L; i++){ cin >> T[i]; T[i]--; } vector<ll> sdist = dijkstra(G, 0), tdist = dijkstra(G, N-1); ll ans = LINF; for(int v : T) if(sdist[v]<=S+E){ ans = min(ans, max(S, sdist[v]) + 1LL + tdist[v]); } if(ans == LINF) cout << -1 << '\n'; else cout << ans << '\n'; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int T=1; //cin >> T; while(T--) solve(); }