题目链接：http://poj.org/problem?id=1502

裸的最短路径。英语。。。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>

using namespace std;

#define MAXV 110
#define INF 100000

int map[MAXV][MAXV],n;
int d[MAXV],vis[MAXV];
int ans;

void dijstra()
{
	for(int i=1;i<=n;i++)
    {
		d[i]=INF;
		vis[i]=0;
	}
	d[1]=0;
	for(int i=1;i<=n;i++)
	{
		int min=INF,v;
		for(int j=1;j<=n;j++)
		{
			if(!vis[j] && d[j]<min)
			{
				min=d[j];
				v=j;
			}
		}
		vis[v]=1;
		for(int j=1;j<=n;j++)
			if(!vis[j] && d[j] > d[v]+map[v][j])
				d[j]=d[v]+map[v][j];
	}
}

int main()
{
	char s[20];
	while(scanf("%d",&n)!=EOF)
    {
        ans == -1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
            {
                if(i!=j) map[i][j]=INF;
				else map[i][j]=0;
            }
		for(int i=2;i<=n;i++)
			for(int j=1;j<i;j++)
            {
				cin>>s;
				if(s[0] != 'x')
					map[i][j]=map[j][i]= atof(s);
			}
		dijstra();
		for(int i=1;i<=n;i++) ans = max(ans,d[i]);
        printf("%d\n",ans);
	}
	return 0;
}