#include <iostream>
using namespace std;
#include <string.h>
#include <stdio.h>
const int size = 110;
#define maxint 99999
class poj1502
{
      private:
              int map[size][size];
              int dist[size];
              bool flag[size];
      public:
             int n;
             void input();
			 void output();
             void dijkstra();
};
int translate(char str[])
{
    int sum=0,k,len;
     if(str[0]=='x')
     return -1;
     else
     {   
         len=strlen(str);
         for(k=0;k<len;k++)
         sum=sum*10+(str[k]-'0');
     }
     return sum;
}
void poj1502::input()
{
     memset(map,0,sizeof(map));
     char w[20];
     int weight;
     for(int i=2;i<=n;i++)
     {
             for(int j=1;j<i;j++)
             {
                     scanf("%s",w);
                    weight=translate(w);
                    if(weight==-1)
                    {
                                  map[i][j]=maxint;
                                  map[j][i]=map[i][j];
                    }
                    else
                    {
                        map[i][j]=weight;
                        map[j][i]=map[i][j];
                    }
             }
     }
}
void poj1502::output()
{
     for(int i=1;i<=n;i++)
     {
             for(int j=1;j<=n;j++)
             {
                     cout<<map[i][j];
             }
             cout<<endl;
     }
}
void poj1502::dijkstra()
{
     int k;
     for(k=1;k<=n;k++)
     dist[k]=map[1][k];
	// output();
     memset(flag,false,sizeof(flag));
     flag[1]=true;
     int min=0;
     for(int i=1;i<n;i++)
     {
             int tmp=maxint;
             for(int j=1;j<=n;j++)
             if(!flag[j]&&dist[j]<tmp)
             {
                                      tmp=dist[j];
                                      k=j;
             }
             flag[k]=true;
			 if(dist[k]>min)
				 min=dist[k];
             for(int j=1;j<=n;j++)
             if(!flag[j]&&(dist[k]+map[k][j])<dist[j])
             dist[j]=dist[k]+map[k][j];
     }
	 cout<<min<<endl;
}
int main()
{
    poj1502 t;
    while(scanf("%d",&t.n)!=EOF)
    {
                   t.input();
                   t.dijkstra();
    }
    return 1;
}

• Re:dijkstra算法oms哦给位！ (16) CatLovers 2015-05-01 16:26:16