学步园

这个写法,我觉得还是有待改进的,因为这是在自己没看别的代码自己捉摸出来的,算法上肯定效率不高,呵呵.

肯定没有用邻接表写的要好咯,,,等一会自己就用邻接表写一个..先把这个代码贴上咯.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <queue>
using namespace std;
#define inf 0x3fffffff

int N,M;
int map[105][105];
int dis[105];
int visit[105];
int in[105];

int SPFA()
{
	queue<int > Q;
	for(int i=1;i<=N;i++)
		dis[i]=inf;
	dis[1]=0;
	Q.push(1);
	visit[1]=1;
	in[1]++;
	while(!Q.empty())
	{
		int temp=Q.front();
		Q.pop();
		visit[temp]=0;
		for(int i=1;i<=N;i++)
		{
			if(!visit[temp]&&map[temp][i]!=0x3f3f3f3f&&dis[i]>dis[temp]+map[temp][i])
			{
				Q.push(i);
				visit[i]=1;
				in[i]++;
				dis[i]=dis[temp]+map[temp][i];
				/*if(in[i]>N)
					return -1;//-1 stands for having negative circles;*/
			}
		}
	}
	return dis[N];
}

int main()
{
	while(scanf("%d%d",&N,&M),N|M)
	{
		memset(map,0x3f,sizeof(map));
		memset(in,0,sizeof(in));
		memset(visit,0,sizeof(visit));
		int aa,bb,val;
		int t=inf;
		for(int i=1;i<=M;i++)
		{
			scanf("%d%d%d",&aa,&bb,&val);
			if(map[aa][bb]>val)
			{
				map[aa][bb]=val;
				map[bb][aa]=val;
			}
		}
		int ans=SPFA();
		printf("%d\n",ans);
	}
	return 0;
}