2344777_ac_122ms_3996k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#define INF 10000000
int n, m, x;
int map[1001][1001];
int visited[1001];
int dis[1001], Dis[1001];

void dij()
{
	int i, t, bt;

	for(i = 0; i < n; i++) 
	{
		visited[i] = 0; 
		dis[i] = -1;
	}
	dis[x] = 0;
	bool done;
	while(1) 
	{
		done = 1; bt=-1;
		for(i = 0; i < n; i++) 
		{
			if(!visited[i]&&dis[i]!=-1)
			{
				if (bt==-1 || dis[i]<bt) 
				{
					t = i;
					bt = dis[i];
				}
				done=0;
			}
		}
		if(done) break;
		for(i = 0; i < n; i++)
		{
			if (map[t][i]!=-1)
				if (dis[i]==-1 || dis[t]+map[t][i]<dis[i])
					dis[i]=dis[t]+map[t][i];
		}
		visited[t]=1;
	}

}

void Dij()
{
	int i, t, bt;

	for(i = 0; i < n; i++) 
	{
		visited[i] = 0; 
		Dis[i] = -1;
	}
	Dis[x] = 0;
	bool done;
	while(1) 
	{
		done = 1; bt=-1;
		for(i = 0; i < n; i++) 
		{
			if(!visited[i]&&Dis[i]!=-1)
			{
				if (bt==-1 || Dis[i]<bt) 
				{
					t = i;
					bt = Dis[i];
				}
				done=0;
			}
		}
		if(done) break;
		for(i = 0; i < n; i++)
		{
			if (map[i][t]!=-1)
				if (Dis[i]==-1 || Dis[t]+map[i][t]<Dis[i])
					Dis[i]=Dis[t]+map[i][t];
		}
		visited[t]=1;
	}

}

int main()
{
	int i;
	int st, ed, w;

	scanf("%d%d%d",&n,&m,&x);
	x--;
	memset(map,-1,sizeof(map));
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d",&st,&ed,&w);
		if(map[st-1][ed-1]==-1||map[st-1][ed-1]>w)
			map[st-1][ed-1] = w;
	}
	dij();Dij();
	int ans = 0;
	for(i = 0; i < n; i++)
	{ 
		if (dis[i] + Dis[i] > ans)
			ans = dis[i] + Dis[i];
	}
	printf("%d",ans);
	return 1;
}