学步园

思路：经典的dijkstra

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define M 105
#define LEN 20
#define MAX 10000000
int map[M][M];

void dij (int n)
{
    int
min_dis[M],flag[M];
    int
i,j,k,min;
    for (i = 0;i
< n;i ++){
       
min_dis[i] = map[0][i];
       
flag[i] = 0;
    }
    flag[0] =
1;
    for (i = 1;i
< n;i ++)
    {
       
min = MAX;
       
for (j = 0;j < n;j ++)
           
if (!flag[j]&&min_dis[j]
< min)
               
{
                   
min = min_dis[j];
                   
k = j;
               
}
       
flag[k] = 1;
       
for (j = 0;j < n;j ++)
           
if (!flag[j] &&
min_dis[k]+map[k][j] < min_dis[j])
               
min_dis[j] = min_dis[k] + map[k][j];
    }
    min =
0;
    for (i = 1;i
< n;i ++)
       
if (min_dis[i] > min)
           
min = min_dis[i];
    printf
("%d\n",min);
}
int main ()
{
    int
n,i,j,len;
    char
str[LEN];
    scanf
("%d",&n);
    for (i = 0;i
< n;i ++)
       
map[i][i] = MAX;
    for (i = 1;i
< n;i ++)
       
for (j = 0;j < i;j ++)
       
{
           
scanf ("%s",str);