喜马拉雅山上的猴子

Time Limit: 1000 MS Memory Limit: 256 MB

Submit Status

余周周告诉我喜马拉雅山上有猴子，他们知道点石成金的方法。我不信，于是余周周带我去喜马拉雅山拜访猴子。

喜马拉雅山上有n个猴子聚落，不妨叫它们1,2，…n号聚落；它们之间有m条单向道路(这意味着如果一条路从1号聚落到2号聚落，那么你不能通过这条路从2号聚落到1号聚落)，每条道路连接2个聚落，且拥有不同的长度。可能有两条道路的起点和终点相同，但没有一条道路的起点和终点是同一个聚落。

因为急切的想要知道点石成金的方法，余周周只想拜访四个猴子聚落，不妨按拜访顺序将它们记为A、B、C、D。当然，为了节省体力，余周周在这些城市(ABCD)之间旅行时会选择最短的路径。不过，喜马拉雅山上的风景不错，所以余周周想要多停留一会，让旅行过程当中经过的路径总长度最长。

余周周觉得自己制定旅行计划太麻烦，于是把任务交给了你。你需要帮她决定ABCD四个聚落的编号以及访问顺序，以满足余周周的要求。

Input

第一行两个整数n,m(4 ≤ n ≤ 1000, 3 ≤ m ≤ 2000), 表示喜马拉雅山上聚落的数量和单向道路的数量。

接下来m行，每行三个整数x,y,z( 1≤ x,y ≤ n, x≠y, 1 ≤ z ≤ 5000 ),表示从x到y有一条距离为z的单向道路。

输入数据保证题目有解。

Output

输出四个整数a,b,c,d，表示你选择的四个聚落的编号，按照访问顺序输出。

a,b,c,d应该各不相同。

如果有多组满足条件的答案，则输出任意一组答案。

Sample input and output

Sample Input	Sample Output
`4 6 1 2 1 2 3 1 3 4 1 1 3 1 1 4 1 2 4 1`	`1 2 3 4`
`6 12 1 6 4 3 4 5 3 2 1 3 1 2 6 5 2 4 5 1 2 5 5 5 3 1 2 3 2 5 1 2 6 2 4 4 1 5`	`1 2 6 4`

Hint

样例1：12,23,34之间的最短路距离都为1，总距离为3，显然最长。

样例2：可能有其他正确答案。

Source

2018 UESTC ACM Training for Graph Theory

题解：最短路问题，找出距离最短的4个点。可以利用spfa最短路解决。A,B,C,D 4个点，显然枚举B，C两点到其他点的最短距离，然后3段加起来，每次保留最小值即可；可以利用优先队列优化，只要取出前3即可；

AC代码为：

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstdio>

using namespace std;

const int INF = 50000000;

struct part {

	int ends, data, next;

};

struct Info {

	int id, v;

	bool operator > (const Info &a) const

	{

		return a.v < v;

	}

	bool operator < (const Info &a) const

	{

		return a.v > v;

	}

};

vector<Info> s[2000], s1[2000];

struct part e[3000];

int i, j, cnt, max1, n, m, x, y, z, ii, jj, a, b, c, d, v, dis[1010][1010], st[3000];

void combine(int x, int y, int z)

{

	cnt += 1;

	e[cnt].ends = y;

	e[cnt].data = z;

	e[cnt].next = st[x];

	st[x] = cnt;

}

void spfa(int t)

{

	for (int i = 1; i <= n; i++) dis[t][i] = INF;

	dis[t][t] = 0;

	queue<int> Q;

	Q.push(t);

	while (!Q.empty())

	{

		int u = Q.front();

		Q.pop();

		for (int i = st[u]; i != -1; i = e[i].next)

		{

			int v = e[i].ends;

			int w = e[i].data;

			if (dis[t][v]>dis[t][u] + w)

			{

				dis[t][v] = dis[t][u] + w;

				Q.push(v);

			}

		}

	}

}

int main()

{

	cin >> n >> m;

	for (i = 1; i <= n; i++)

		st[i] = -1;

	cnt = 0;

	for (i = 1; i <= m; i++)

	{

		cin >> x >> y >> z;

		combine(x, y, z);

	}

	for (i = 1; i <= n; i++) spfa(i);

	for (i = 1; i <= n; i++)

	{

		for (j = 1; j <= n; j++)

			if (dis[i][j] != INF) s[i].push_back(Info {j,dis[i][j]});

	}

	for (j = 1; j <= n; j++)

	{

		for (i = 1; i <= n; i++)

			if (dis[i][j] != INF) s1[j].push_back(Info {i,dis[i][j]});

	}

	for (i = 1; i <= n; i++)

	{

		sort(s[i].begin(), s[i].end(), greater<Info>());

		sort(s1[i].begin(), s1[i].end(), greater<Info>());

	}

	max1 = -10000;

	for (i = 1; i <= n; i++)

	{

		for (j = 1; j <= n; j++)

			if (i != j && dis[i][j] != INF)

			{

				v = 0;

				for (size_t it = 0; it<s1[i].size(); it++)

				{

					for (size_t itt = 0; itt<s[j].size(); itt++)

						if (s1[i][it].id != s[j][itt].id&&s1[i][it].id != i && s1[i][it].id != j && i != s[j][itt].id&&j != s[j][itt].id)

						{

							if (s1[i][it].v + dis[i][j] + s[j][itt].v>max1)

							{

								max1 = s1[i][it].v + dis[i][j] + s[j][itt].v;

								a = s1[i][it].id;

								b = i;

								c = j;

								d = s[j][itt].id;

							}

							v = 1;

							break;

						}

					if (v == 1) break;

				}

			}

	}

	printf("%d %d %d %d\n", a, b, c, d);

	return(0);

}<iostream>

#include<queue>

#include<algorithm>

#include<cstdio>

using namespace std;

const int INF = 50000000;

struct part {

	int ends, data, next;

};

struct Info {

	int id, v;

	bool operator > (const Info &a) const

	{

		return a.v < v;

	}

	bool operator < (const Info &a) const

	{

		return a.v > v;

	}

};

vector<Info> s[2000], s1[2000];

struct part e[3000];

int i, j, cnt, max1, n, m, x, y, z, ii, jj, a, b, c, d, v, dis[1010][1010], st[3000];

void combine(int x, int y, int z)

{

	cnt += 1;

	e[cnt].ends = y;

	e[cnt].data = z;

	e[cnt].next = st[x];

	st[x] = cnt;

}

void spfa(int t)

{

	for (int i = 1; i <= n; i++) dis[t][i] = INF;

	dis[t][t] = 0;

	queue<int> Q;

	Q.push(t);

	while (!Q.empty())

	{

		int u = Q.front();

		Q.pop();

		for (int i = st[u]; i != -1; i = e[i].next)

		{

			int v = e[i].ends;

			int w = e[i].data;

			if (dis[t][v]>dis[t][u] + w)

			{

				dis[t][v] = dis[t][u] + w;

				Q.push(v);

			}

		}

	}

}

int main()

{

	cin >> n >> m;

	for (i = 1; i <= n; i++)

		st[i] = -1;

	cnt = 0;

	for (i = 1; i <= m; i++)

	{

		cin >> x >> y >> z;

		combine(x, y, z);

	}

	for (i = 1; i <= n; i++) spfa(i);

	for (i = 1; i <= n; i++)

	{

		for (j = 1; j <= n; j++)

			if (dis[i][j] != INF) s[i].push_back(Info {j,dis[i][j]});

	}

	for (j = 1; j <= n; j++)

	{

		for (i = 1; i <= n; i++)

			if (dis[i][j] != INF) s1[j].push_back(Info {i,dis[i][j]});

	}

	for (i = 1; i <= n; i++)

	{

		sort(s[i].begin(), s[i].end(), greater<Info>());

		sort(s1[i].begin(), s1[i].end(), greater<Info>());

	}

	max1 = -10000;

	for (i = 1; i <= n; i++)

	{

		for (j = 1; j <= n; j++)

			if (i != j && dis[i][j] != INF)

			{

				v = 0;

				for (size_t it = 0; it<s1[i].size(); it++)

				{

					for (size_t itt = 0; itt<s[j].size(); itt++)

						if (s1[i][it].id != s[j][itt].id&&s1[i][it].id != i && s1[i][it].id != j && i != s[j][itt].id&&j != s[j][itt].id)

						{

							if (s1[i][it].v + dis[i][j] + s[j][itt].v>max1)

							{

								max1 = s1[i][it].v + dis[i][j] + s[j][itt].v;

								a = s1[i][it].id;

								b = i;

								c = j;

								d = s[j][itt].id;

							}

							v = 1;

							break;

						}

					if (v == 1) break;

				}

			}

	}

	printf("%d %d %d %d\n", a, b, c, d);

	return(0);

}

巴特西

四点之间最短路（spfa+优先队列+枚举优化）UESTC1955喜马拉雅山上的猴子