题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544

Dijkstra版本：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
const int INF =0xfffffff;
int G[N][N];
int d[N];
bool vis[N];
int n,m;
void Dijkstra(int s){
    fill(d,d+N,INF);
    d[s] = 0;
    for(int i = 1; i <= n; i++){
        int u = -1,MIN = INF;
        for(int j = 1; j <= n; j++){
            if(vis[j] == false&& d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1) return; //说明剩下的顶点和s不连通
        vis[u] = true;
        for(int v = 1; v <= n; v++){
            if(vis[v] == false && G[u][v] != INF&&d[u]+G[u][v] < d[v]){
                d[v] = d[u]+G[u][v];
            }
        } 
    }

}
int main(){
    int u,v,w;
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        fill(G[1],G[1]+N*N,INF);
        fill(vis,vis+N,false);
        for(int i = 0; i < m; i++){
            cin>>u>>v>>w;
            G[u][v]=G[v][u]=w;
        }
        Dijkstra(1);
        printf("%d\n",d[n]);
    }

    return 0;
}

Floyd版本：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 105;
const int INF = 0x3fffffff;
int dis[N][N];  
int n,m;
void Floyd(){
    for(int k =0;k < n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j] < dis[i][j]){
                    dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }
}
int main(){

    int u,v,w;
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        fill(dis[0],dis[0]+N*N,INF);
        for(int i=0;i<n;i++){
            dis[i][i] = 0;
        }
        for(int i=0;i<m;i++){
            cin>>u>>v>>w;
            dis[u-1][v-1] = w;
            dis[v-1][u-1] = w; 
        }
        Floyd();

        cout<<dis[0][n-1]<<endl;
    }



    return 0;
}