版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/43276929

题目链接： 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;
}