pku2387.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 75 行

#include <stdio.h>
#define TheMax 100000000

int path[2001][2001];
int mindis[2001], use[2001];
int N, T;

void DIJ()
{
	int i, j, k ,min, u;
	
	for (i = 0; i < N; i++)
	{
		use[i] = 0;
		mindis[i] = path[i][0];
	}

	use[0] = 1;

	for (j = 1; j < N; j++)
	{
		min = TheMax;
		k = 0;

		for (i = 0; i < N; i++)
		{
			if (!use[i] && min > mindis[i])
			{
				u = i;
				min = mindis[i];
			}
		}

		use[u] = 1;

		for (i = 1; i < N; i++)
		{
			if (!use[i] && mindis[i] > min + path[u][i])
			{
				mindis[i] = min + path[u][i];
			}
		}
	}
	printf("%d\n", mindis[N - 1]);
}

int main()
{
	int i, j, s, e, d;
		scanf("%d %d", &T, &N);
		for (i = 0; i < N; i++)
		{
			for (j = i + 1; j < N; j++)
			{
				path[i][j] = path[j][i] = TheMax;
			}
			path[i][i] = 0;
		}

		for (i = 0; i < T; i++)
		{
			scanf("%d %d %d", &s, &e, &d);
			if (path[s - 1][e - 1] > d)
			{
				path[s - 1][e - 1] = d;
				path[e - 1][s - 1] = d;
			}
		}

		DIJ();

	return 0;
}