結果
問題 | No.848 なかよし旅行 |
ユーザー | どらら |
提出日時 | 2019-07-07 15:54:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 1,508 bytes |
コンパイル時間 | 1,853 ms |
コンパイル使用メモリ | 177,300 KB |
実行使用メモリ | 11,304 KB |
最終ジャッジ日時 | 2024-11-08 00:58:55 |
合計ジャッジ時間 | 4,539 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 162 ms
10,720 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 | 3 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 | 48 ms
5,896 KB |
testcase_12 | AC | 65 ms
6,880 KB |
testcase_13 | AC | 92 ms
8,040 KB |
testcase_14 | AC | 23 ms
5,248 KB |
testcase_15 | AC | 86 ms
7,952 KB |
testcase_16 | AC | 159 ms
11,304 KB |
testcase_17 | AC | 106 ms
8,836 KB |
testcase_18 | AC | 47 ms
5,616 KB |
testcase_19 | AC | 39 ms
5,324 KB |
testcase_20 | AC | 12 ms
5,248 KB |
testcase_21 | AC | 130 ms
10,204 KB |
testcase_22 | AC | 149 ms
10,652 KB |
testcase_23 | AC | 11 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 158 ms
9,740 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 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; ll N, M, P, Q, T; vector<pair<ll,ll>> G[2005]; void dijkstra(vector<ll>& dist, ll st){ vector<bool> visited(N+1, false); priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q; q.push(make_pair(0,st)); while(!q.empty()){ pair<ll,ll> p = q.top(); q.pop(); if(visited[p.second]) continue; visited[p.second] = true; dist[p.second] = p.first; FOR(it,G[p.second]){ if(!visited[it->first]){ q.push(make_pair(p.first + it->second, it->first)); } } } } int main(){ cin >> N >> M >> P >> Q >> T; rep(i,M){ ll a, b, c; cin >> a >> b >> c; G[a].emplace_back(b, c); G[b].emplace_back(a, c); } vector<ll> dist_st(N+1,-1), dist_P(N+1,-1), dist_Q(N+1,-1); dijkstra(dist_st, 1); dijkstra(dist_P, P); dijkstra(dist_Q, Q); ll ret = -1; if(dist_st[P] + dist_P[Q] + dist_st[Q] <= T){ ret = T; } REP(x,1,N+1){ REP(y,1,N+1){ ll sum = dist_st[x]; sum += max(dist_P[x] + dist_P[y], dist_Q[x] + dist_Q[y]); sum += dist_st[y]; if(sum <= T){ ret = max(ret, T - max(dist_P[x] + dist_P[y], dist_Q[x] + dist_Q[y])); } } } cout << ret << endl; return 0; }