floyd怎么错了
查看原帖
floyd怎么错了
332914
happybob楼主2021/12/21 17:49
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int p, F, c;
const int N = 505;
int f[N];
int dis[N][N];

void Init()
{
	for (int i = 1; i <= p; i++)
	{
		for (int j = 1; j <= p; j++)
		{
			dis[i][j] = 0x7f;
		}
		dis[i][i] = 0;
	}
}

void floyd()
{
	for (int k = 1; k <= p; k++)
	{
		for (int i = 1; i <= p; i++)
		{
			for (int j = 1; j <= p; j++)
			{
				if (i != j && j != k && i != k)
				{
					dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
				}
			}
		}
	}
}

int main()
{
	Init();
	cin >> p >> F >> c;
	for (int i = 1; i <= F; i++)
	{
		cin >> f[i];
	}
	for (int i = 1; i <= c; i++)
	{
		int o, q, l;
		cin >> o >> q >> l;
		dis[o][q] = l;
		dis[q][o] = l;
	}
	floyd();
	int place = 0, minn = 1e8;
	for (int i = 1; i <= p; i++)
	{
		int sum = 0;
		for (int j = 1; j <= F; j++)
		{
			sum += dis[i][f[j]];
		}
		if (sum < minn)
		{
			minn = sum;
			place = i;
		}
	}
	cout << place << endl;
	return 0;
}
2021/12/21 17:49
加载中...