【？？？？】最短路(short)

问题描述：

给出N个点，M条无向边的简单图，问所有点对之间的最短路。

数据输入：

第1行两个正整数N，M（N<=100，M<=5000）

下面M行，每行3个正整数x, y, w，为一条连接顶点x与y的边权值为w。(x<=n，y<=n，w<=1000)

数据输出：

包括N行，每行N个数，第i行第j个数为点i到点j的最短路，第i行第i个数应为0，数字之间空格隔开。

样例输入：

5 10

3 2 1

2 4 7

5 3 4

4 1 2

5 1 8

3 4 10

5 4 9

2 5 2

1 2 1

3 1 10

样例输出：

0 1 2 2 3

1 0 1 3 2

2 1 0 4 3

2 3 4 0 5

3 2 3 5 0

【题解】

求任意两点之间的最短路径。只要用floyd算法就能实现。

然后一开始置初值w[i][j]的时候。

对于输入的x,y,z只有在w[x][y] > z时才更新w[x][y]为z。

这样保证输入的数据设置的w[x][y]是x到y的最短距离。

【代码】

#include <cstdio>

#include <cstring>

int n, m,w[101][101];

void input_data()

{

	memset(w, 127 / 3, sizeof(w)); //这是一个很大的接近210000000的数字把它除3防止溢出

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= m; i++) //输入 m条边

	{

		int x,y,z;

		scanf("%d%d%d", &x, &y, &z);

		if (w[x][y] > z) //如果x,y之间的距离更短了则更新

		{

			w[x][y] = z;

			w[y][x] = z;

		}

	}

}

void get_ans()

{

	for (int i = 1; i <= n; i++) //i到i的距离设置为0

		w[i][i] = 0;

	for (int k = 1; k <= n; k++) //用floyd求任意两点之间的距离。

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

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

				if (w[i][j] > w[i][k] + w[k][j])

					w[i][j] = w[i][k] + w[k][j];

}

void output_ans()

{

	for (int i = 1; i <= n; i++) //用邻接矩阵的方式输出任意两点之间的距离即可。

	{

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

			printf("%d ", w[i][j]);

		printf("%d\n", w[i][n]);

	}

}

int main()

{

	input_data();

	get_ans();

	output_ans();

	return 0;

}

巴特西

【？？？？】最短路(short)

最新文章

热门文章