結果

問題 No.848 なかよし旅行
コンテスト
ユーザー zelda_master
提出日時 2026-07-26 15:23:02
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 57 ms / 2,000 ms
+ 145µs
コード長 1,638 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,275 ms
コンパイル使用メモリ 191,640 KB
実行使用メモリ 8,384 KB
最終ジャッジ日時 2026-07-26 15:23:07
合計ジャッジ時間 3,716 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;

const int N = 2010, M = 200010;

bool st[N];
LL d[3][N];
priority_queue<PLI, vector<PLI>, greater<PLI>> pq;
int n, m, p, q, t, h[N], e[M], ne[M], w[M], idx;

void Add(int x, int y, int z) {
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

void Dijkstra(int S, LL dd[]) {
    memset(st, 0, sizeof(st));
    pq.push({ 0LL, S }), dd[S] = 0LL;
    while (!pq.empty()) {
        auto [dist, u] = pq.top(); pq.pop();
        if (st[u]) continue;
        st[u] = true;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dd[v] > dist + w[i]) {
                dd[v] = dist + w[i];
                pq.push({ dd[v], v });
            }
        }
    }
}

int main() {
    // freopen("friend.in", "r", stdin);
    // freopen("friend.out", "w", stdout);

    scanf("%d%d%d%d%d", &n, &m, &p, &q, &t);
    memset(h, -1, sizeof(h));
    for (int i = 1, a, b, c; i <= m; ++i) {
        scanf("%d%d%d", &a, &b, &c);
        Add(a, b, c), Add(b, a, c);
    }

    memset(d, 0x3f, sizeof(d));
    Dijkstra(1, d[0]), Dijkstra(p, d[1]), Dijkstra(q, d[2]);
    if (d[0][p] + d[0][q] + d[1][q] <= t) printf("%d\n", t);
    else {
        LL ans = -1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                LL ti = d[0][i] + max(d[1][i] + d[1][j], d[2][i] + d[2][j]) + d[0][j];
                if (ti <= t) ans = max(ans, d[0][i] + d[0][j] + t - ti);
            }
        }
    
        printf("%lld\n", ans);
    }
    
    return 0;
}
0