POJ 2387 Til the Cows Come Home (Dijkstra)

题目大意：

给定无向图，要求输出从点n到点1的最短路径。

注意有重边，要取最小的。

水题。。对于无向图，从1到n和n到1是一样的。

直接Dijkstra即可

#include<cstdio>

#include<cstring>

const int MAXN=1000+10;

const int INF=999999;

int map[MAXN][MAXN];

int dis[MAXN];

int main()

{

	int n,t;

	while(~scanf("%d%d",&t,&n))

	{

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

		{

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

				map[i][j]=INF;

			dis[i]=INF;

		}

		int from,to,len;

		for(int i=0;i<t;i++)

		{

			scanf("%d%d%d",&from,&to,&len);

			if(len < map[from][to])

				map[from][to]=map[to][from]=len;

		}

		//Dijkstra

		bool vis[MAXN]={0};

		int cur=n;			//这里如果为1，那么输出改为dis[n]

		vis[cur]=true;

		dis[cur]=0;

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

		{

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

			{

				if( map[cur][j]!=INF && dis[cur]+ map[cur][j] < dis[j])

					dis[j]=dis[cur]+ map[cur][j];

			}

			int min=INF;

			for(int j=1;j<=n;j++)//find the next minimum

			{

				if( !vis[j] && dis[j] < min)

					min=dis[cur = j];

			}

			vis[cur]=true;

		}

		printf("%d\n",dis[1]);

	}

}

巴特西

POJ 2387 Til the Cows Come Home (Dijkstra)

最新文章

热门文章