結果

問題 No.848 なかよし旅行
ユーザー kimiyuki
提出日時 2019-07-05 23:27:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 156 ms / 2,000 ms
コード長 2,621 bytes
コンパイル時間 2,411 ms
コンパイル使用メモリ 208,532 KB
最終ジャッジ日時 2025-01-07 06:12:56
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
#define dump(x) cerr << #x " = " << x << endl
using ll = long long;
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
template <typename X, typename T> auto make_vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_vectors(X x, Y y, Z z, Zs... zs) { auto cont = make_vectors(y, z, zs...); 
    return vector<decltype(cont)>(x, cont); }
template <typename T> ostream & operator << (ostream & out, vector<T> const & xs) { REP (i, (int)xs.size() - 1) out << xs[i] << ' '; if (not xs.empty
    ()) out << xs.back(); return out; }
vector<ll> dijkstra(vector<vector<pair<int, ll> > > const & g, int root) {
    vector<ll> dist(g.size(), LLONG_MAX);
    priority_queue<pair<ll, int> > que;
    dist[root] = 0;
    que.emplace(- dist[root], root);
    while (not que.empty()) {
        ll dist_i; int i; tie(dist_i, i) = que.top(); que.pop();
        if (dist[i] < - dist_i) continue;
        for (auto it : g[i]) {
            int j; ll cost; tie(j, cost) = it;
            if (- dist_i + cost < dist[j]) {
                dist[j] = - dist_i + cost;
                que.emplace(dist_i - cost, j);
            }
        }
    }
    return dist;
}
ll solve(int n, int m, int p, int q, ll t, const vector<vector<pair<int, ll> > > & g) {
    auto dist_0 = dijkstra(g, 0);
    auto dist_p = dijkstra(g, p);
    auto dist_q = dijkstra(g, q);
    ll ans = -1;
    if (dist_0[p] + dist_p[q] + dist_0[q] <= t) {
        ans = t;
    }
    REP (x, n) REP (y, n) {
        ll total = dist_0[x] + max(dist_p[x] + dist_p[y], dist_q[x] + dist_q[y]) + dist_0[y];
        if (total <= t) {
            chmax(ans, dist_0[x] + dist_0[y] + (t - total));
        }
    }
    return ans;
}
int main() {
    int n, m, p, q; ll t; cin >> n >> m >> p >> q >> t;
    -- p; -- q;
    vector<vector<pair<int, ll> > > g(n);
    REP (i, m) {
        int a, b; ll c; cin >> a >> b >> c;
        -- a; -- b;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    cout << solve(n, m, p, q, t, g) << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0