結果

問題 No.2805 Go to School
ユーザー InTheBloom
提出日時 2024-07-12 22:28:58
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 341 ms / 2,000 ms
コード長 2,232 bytes
コンパイル時間 1,719 ms
コンパイル使用メモリ 103,300 KB
実行使用メモリ 18,912 KB
最終ジャッジ日時 2024-07-16 01:41:02
合計ジャッジ時間 7,975 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
constexpr int iINF = 1'000'000'000;
constexpr ll llINF = 1'000'000'000'000'000'000;
int main () {
int N, M, L, S, E; cin >> N >> M >> L >> S >> E;
vector<vector<pair<int, int>>> graph(N);
for (int i = 0; i < M; i++) {
int a, b, t; cin >> a >> b >> t;
a--, b--;
graph[a].push_back(make_pair(b, t));
graph[b].push_back(make_pair(a, t));
}
vector<int> T(L);
for (int i = 0; i < L; i++) cin >> T[i];
for (int i = 0; i < L; i++) T[i]--;
//
auto cmp = [&] (pair<int, ll>& a, pair<int, ll>& b) {
return b.second < a.second;
};
priority_queue<pair<int, ll>, vector<pair<int, ll>>, decltype(cmp)> pq(cmp);
vector<ll> home_to(N, llINF);
pq.push(make_pair(0, 0LL));
while (!pq.empty()) {
auto pos = pq.top(); pq.pop();
int u = pos.first; ll c = pos.second;
if (home_to[u] < c) continue;
home_to[u] = c;
for (auto to : graph[u]) {
int v = to.first;
ll new_cost = c + to.second;
if (home_to[v] <= new_cost) continue;
home_to[v] = new_cost;
pq.push(make_pair(v, new_cost));
}
}
vector<ll> school_to(N, llINF);
pq.push(make_pair(N - 1, 0LL));
while (!pq.empty()) {
auto pos = pq.top(); pq.pop();
int u = pos.first; ll c = pos.second;
if (school_to[u] < c) continue;
school_to[u] = c;
for (auto to : graph[u]) {
int v = to.first;
ll new_cost = c + to.second;
if (school_to[v] <= new_cost) continue;
school_to[v] = new_cost;
pq.push(make_pair(v, new_cost));
}
}
ll ans = llINF;
for (auto i : T) {
if (home_to[i] == llINF || school_to[i] == llINF) continue;
if (S + E <= home_to[i]) continue; // ...
ans = min(ans, max(1LL * S, home_to[i]) + 1 + school_to[i]);
}
if (ans == llINF) {
cout << -1 << "\n";
}
else {
cout << ans << "\n";
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0