3058331_ac_0ms_192k.cpp

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

#include <stdio.h>
#include <algorithm>
#define inf 2100000000

using namespace std;

int f, m;
int map[101][101];
int dis[101];
int mark[101];

void solve()
{
	int i, j, v;
	int min;

	for(i = 0; i < f; i++)
	{
		dis[i] = inf;
		mark[i] = 0;
	}
	dis[0] = 0;
	for(i = 0; i < f; i++)
	{
		min = inf;
		for(j = 0; j < f; j++)
		{
			if(!mark[j]&&dis[j]<min)
			{
				min = dis[j];
				v = j;
			}
		}
		mark[v] = 1;
		for(j = 0; j < f; j++)
		{
			if(map[v][j]!=0&&dis[v]+map[v][j]<dis[j])
			{
				dis[j] = dis[v]+map[v][j];
			}
		}
	}
}

int main()
{
	int i, j;
	char tmp[10];

	scanf("%d",&f);
	memset(map,0,sizeof(map));
	for(i = 1; i < f; i++)
	{
		for(j = 0; j < i; j++)
		{
			scanf("%s",tmp);
			if(tmp[0]!='x')
			{
				map[i][j] = map[j][i] = atoi(tmp);
			}
		}
	}
	solve();
	int ans = -1;
	for(i = 0; i < f; i++)
	{
		if(dis[i]!=inf&&dis[i]>ans)
		{
			ans = dis[i];
		}
	}
	printf("%d\n",ans);
	return 0;
}