結果

問題 No.848 なかよし旅行
コンテスト
ユーザー rabimea
提出日時 2025-09-28 07:54:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 1,608 bytes
コンパイル時間 3,676 ms
コンパイル使用メモリ 290,484 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-28 07:54:30
合計ジャッジ時間 5,346 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>

using std::cin, std::cout, std::cerr;
using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    int n, m, p, q, t;
    cin >> n >> m >> p >> q >> t;
    std::vector<std::vector<std::pair<int, int>>> e(n + 1);
    for(int i = 1; i <= m; i ++) {
        int u, v, w; cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    std::vector<ll> d(n + 1), dp(n + 1), dq(n + 1);
    auto dijkstra = [&](int s, std::vector<ll> &d) {
        std::set<std::pair<ll, int>> set;
        d.assign(n + 1, 1e18L);
        d[s] = 0;
        for(int i = 1; i <= n; i ++)
            set.insert({d[i], i});
        while(!set.empty()) {
            int x = set.begin()->second;
            set.erase(set.begin());
            for(auto [i, w] : e[x]) {
                if(d[x] + w < d[i]) {
                    set.erase({d[i], i});
                    d[i] = d[x] + w;
                    set.insert({d[i], i});
                }
            }
        }
    };
    dijkstra(1, d);
    dijkstra(p, dp);
    dijkstra(q, dq);

    ll ans = -1;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            ll sep = std::max(dp[i] + dp[j], dq[i] + dq[j]);
            bool ok = d[i] + d[j] + sep <= t;
            if(ok) {
                if(ans == -1 || ans < t - sep)
                    ans = t - sep;
            }
        }
    }
    if(d[p] + d[q] + dp[q] <= t)
        ans = t;
    cout << ans << '\n';
}
0