結果

問題 No.848 なかよし旅行
ユーザー wunderkammer2wunderkammer2
提出日時 2019-12-26 12:43:42
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 2,751 bytes
コンパイル時間 1,225 ms
コンパイル使用メモリ 107,532 KB
実行使用メモリ 8,688 KB
最終ジャッジ日時 2024-04-25 14:09:52
合計ジャッジ時間 3,487 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
8,688 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,948 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 32 ms
6,940 KB
testcase_12 AC 42 ms
6,940 KB
testcase_13 AC 60 ms
6,944 KB
testcase_14 AC 19 ms
6,944 KB
testcase_15 AC 56 ms
6,940 KB
testcase_16 AC 98 ms
7,296 KB
testcase_17 AC 69 ms
6,940 KB
testcase_18 AC 33 ms
6,940 KB
testcase_19 AC 29 ms
6,944 KB
testcase_20 AC 5 ms
6,940 KB
testcase_21 AC 84 ms
7,040 KB
testcase_22 AC 89 ms
6,944 KB
testcase_23 AC 11 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 101 ms
7,680 KB
testcase_26 AC 2 ms
6,944 KB
testcase_27 AC 2 ms
6,940 KB
testcase_28 AC 1 ms
6,944 KB
testcase_29 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

typedef pair<int, int> P;
const int INF = 1000000000;

struct edge
{
	int to;
	int cost;
};


vector<ll> dijkstra(int start, vector<vector<edge>> edges)
{
	vector<ll> d(edges.size(), INF);

	//最短距離が小さい順に取り出したいので、
	//P.firstを最短距離、P.secondをノード、として、
	//greater<P>を使用。
	priority_queue<P, vector<P>, greater<P>> costs;
	costs.push(P(0, start));
	d[start] = 0;

	while (!costs.empty())
	{
		P p = costs.top(); costs.pop();
		int v = p.second;

		if (d[v] < p.first) continue;

		for (auto e : edges[v])
		{
			int cost = d[v] + e.cost;
			if (cost < d[e.to])
			{
				d[e.to] = cost;
				costs.push(P(cost, e.to));
			}
		}
	}

	return d;
}

int main()
{	
	int N, M, P, Q, T;
	cin >> N >> M >> P >> Q >> T;

	vector<vector<edge>> edges(N + 1, vector<edge>());

	rep(i, M)
	{
		int a, b, c;
		cin >> a >> b >> c;

		edges[a].emplace_back(edge{ b, c });
		edges[b].emplace_back(edge{ a, c });
	}


	auto from1 = dijkstra(1, edges);
	auto fromP = dijkstra(P, edges);
	auto fromQ = dijkstra(Q, edges);

	//2人で一緒に回ることができるか確認
	//1→P→Q→1のルートが制限時間内に終わるか？
	if (from1[P] + fromP[Q] + from1[Q] <= T)
	{
		cout << T << endl;
		return 0;
	}

	//2人で間に合わない場合は別々に行く。
	//P・Qへ最短ルートで行く。
	
	//1からP・Qそれぞれを最短ルートで往復して間に合わない場合
	if (2 * max(from1[P], from1[Q]) > T)
	{
		cout << -1 << endl;
		return 0;
	}

	//上記以外は2人が別々に行動する。
	//以下の全探索で計算可能。
	//一人目：1→x→P→y→1
	//二人目：1→x→Q→y→1

	ll maxCost = -1;
	reple(x, 1, N)
	{
		reple(y, 1, N)
		{
			//一緒に行動する時間
			ll cost1 = from1[x] + from1[y];

			//別行動する時間（最大）
			ll cost2 = max(fromP[x] + fromP[y], fromQ[x] + fromQ[y]);

			if (cost1 + cost2 <= T)
			{
				//T = 一緒に行動する時間 + 別行動する時間 + それ以外（同じ場所で待つ時間）なので、
				//一緒に行動する時間 + それ以外（同じ場所で待つ時間） = T - 別行動する時間
				maxCost = max(maxCost, T - cost2);
			}
		}
	}

	cout << maxCost << endl;
	return 0;
}
0