#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;
} 

• table [ j ] [min ]<maxint 少写个p (2069) RedField 2006-10-28 23:32:32
  • 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