結果

問題 No.848 なかよし旅行
ユーザー kimiyukikimiyuki
提出日時 2019-07-05 23:27:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 159 ms / 2,000 ms
コード長 2,621 bytes
コンパイル時間 2,318 ms
コンパイル使用メモリ 214,836 KB
実行使用メモリ 10,716 KB
最終ジャッジ日時 2024-11-08 00:51:57
合計ジャッジ時間 4,491 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 159 ms
10,716 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 4 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 33 ms
5,248 KB
testcase_12 AC 45 ms
5,632 KB
testcase_13 AC 61 ms
6,656 KB
testcase_14 AC 17 ms
5,248 KB
testcase_15 AC 57 ms
6,528 KB
testcase_16 AC 101 ms
8,320 KB
testcase_17 AC 70 ms
7,296 KB
testcase_18 AC 33 ms
5,248 KB
testcase_19 AC 29 ms
5,248 KB
testcase_20 AC 11 ms
5,248 KB
testcase_21 AC 87 ms
7,424 KB
testcase_22 AC 93 ms
7,296 KB
testcase_23 AC 21 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 109 ms
8,320 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0