#include<iostream>
#include<fstream>
#include<iomanip>
#define MAXNUM 101
using namespace std;

unsigned int Edge[1001][1001];
unsigned int dist[1001];
bool s[1001];

void shortPath(int n,int v){
    int i,j,w;
    for(i=1;i<=n;i++){
        dist[i]=Edge[i][v];
        s[i]=0;
    }
    s[v]=1;dist[v]=0;
    for(i=0;i<n-1;i++){
        unsigned int min=MAXNUM;
        int u=v;
        for(j=1;j<=n;j++){
            if(!s[j]&&dist[j]<min){
                u=j;
                min=dist[j];
            }
        }
        s[u]=1;
        for(w=1;w<=n;w++){
            if( !s[w] &&  Edge[u][w]<MAXNUM && dist[w]>Edge[u][w]+dist[u]){
                dist[w]=Edge[u][w]+dist[u];
            }
        }
    }
}

int main(){
    int T,N;
    //ifstream cin("tmp.txt");
    cin>>T>>N;
    int i,j;
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            Edge[i][j]=MAXNUM;
        }
    }
    for(i=1;i<=N;i++){
        Edge[i][i]=0;
    }    
    for(i=0;i<T;i++){
        int x,y,tmp;
        scanf("%d %d %d",&x,&y,&tmp);
        if(tmp<Edge[x][y]){
            Edge[x][y]=tmp;
            Edge[y][x]=tmp;
        }
    }
    shortPath(N,N);
    /* for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            cout<<setw(5)<<Edge[i][j]<<' ';
        }
        cout<<endl;
    }    */ 
    cout<<dist[1]<<endl;
    system("pause");
    return 0;
}            
                
                                

• 你的代码可以过的……MAXNUM就101太吝啬了点吧？换成大的，2147483647就好了 (1621) 00448264 2005-04-20 13:43:54
  • 借鉴 (15) y05yxg 2007-05-17 13:22:23
• 我用你的代码过了,把MAXNUM改到了1000000000,然后改成了多组输入,其他都一样 (1670) whusnoopy 2006-05-17 17:23:20
  • 一组输入就够 (0) beyonlin_SCUT 2006-10-12 13:21:58