> #include <string.h> 
> #include <iostream>
> using namespace std;
> const int maxn = 4110;
> const int maxint = 10000001;
> unsigned int nearvex[ maxn ],lowcost[ maxn ],table[ maxn ][ maxn ];  
> int n , tt;
> 
> void Dijkstra(int st,int end) 
> { 
>         int i,j;          
>         for(i=1;i<=n;i++) 
>                {
>                         nearvex[i] = 0; 
>                         lowcost[i] = table[ i ][st]; 
>              }
>           nearvex[ st ] = 1;
>           lowcost [ st ] = 0; 
>         for(i=1;i<=n;i++) 
>         { 
>                 int min = maxint; 
>                 int pmin = -1; 
>                 for(j=1;j<=n;j++) 
>                         if(nearvex[j] != 1 && lowcost[j] < min ) 
>                         { 
>                                 min = lowcost[j]; 
>                                 pmin = j; 
>                         } 
>                    if ( end == pmin ) return ; 
>                 if( pmin >=0 ) 
>                 {
>                     nearvex[pmin] = 1; 
>                      for(j=1;j<=n;j++) 
>                          if(nearvex[j] ==0  && (lowcost[pmin] + table[ j ][ pmin ] < lowcost[j]) &&  table [ j ] [min ]<maxint ) 
>                                 lowcost[j] = lowcost[pmin] + table[j][pmin]; 
>                 }             
>         } 
> } 
> 
> int main() 
> { 
>     int i , j , index1 , index2 , tmp;
>    cin>>n>>tt;
>         for ( i = 1 ; i <= n ; i ++ ) 
>             for ( j = 1 ; j <=n ; j ++ ) 
>                     table [ i ] [ j ] = table [ j ] [ i ] = maxint;
>         for ( i = 1 ; i <=n ; i ++ ) 
>             table [ i ] [ i ] = 0;
>                 
>         for ( i = 0 ; i < tt ; i ++ ) 
>         {  
>             cin>>index1>>index2>>tmp; 
>             if ( tmp < table [ index1 ] [index2 ] ) 
>                 table [ index1 ] [ index2 ] = table [ index2 ]  [index1 ]= tmp;
>         }
>         Dijkstra(1,n); 
>         cout<<lowcost [ n ] <<endl;
>    //cin>>n;
>     return 0;
> } 

• Re: table [ j ] [min ]<maxint 少写个p (25) secretsh 2006-10-28 23:34:52
  • 看来你最近果然是低谷，先读入的是边数。。 (29) RedField 2006-10-28 23:39:36
    • 无语了……一晚上啊一晚上……全搭这题上了……哭死我了…… (0) secretsh 2006-10-28 23:43:10