floyd 算法，最慢最好写

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 110 ;
int dp[N][N] ;

int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m) , n){
        memset(dp,0x3f,sizeof dp) ;

        for(int i = 0 ; i < m ; i++){
            int a,b,c ;
            scanf("%d %d %d",&a,&b,&c) ;
            if(dp[a][b] > c){
                dp[a][b] = dp[b][a] = c ;
            }
        }

        for(int k = 1;  k <= n ; k++){
            for(int i = 1 ; i <= n ; i++){
                if(dp[i][k] != 0x3f3f3f3f){
                    for(int j = 1 ; j <= n ; j++){
                        if(dp[i][j] > dp[i][k] + dp[k][j]){
                            dp[i][j] = dp[i][k] + dp[k][j] ;
                        }
                    }
                }
            }
        }
        cout << dp[1][n] << endl ;
    }
    return 0;
}

dijkstra写法，普通版本，用邻接矩阵存路径

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 110 ;
int n,m ;
int g[N][N] ;
int dist[N] ;
bool st[N] ;

void dijkstra(){
    for(int i = 0 ; i <= n ; i++) dist[i] = 0x3f3f3f3f ;
    dist[1] = 0 ;

    for(int i = 0 ; i < n ; i++){
        int mind = 0x3f3f3f3f ,id = 1 ;
        for(int j = 1 ; j <= n ; j++){
            if(!st[j] && dist[j] < mind){
                mind = dist[j] ;
                id = j ;
            }
        }
        st[id] = 1 ;
        for(int j = 1 ;j <= n ; j++) dist[j] = min(dist[j],dist[id] + g[id][j]) ;
    }
}

int main()
{
    while(scanf("%d %d",&n,&m), n){
        memset(g,0x3f,sizeof g) ;
        memset(st,0,sizeof st) ;

        for(int i = 0 ; i < m ; i++){
            int a,b,c ;
            scanf("%d %d %d",&a,&b,&c) ;
            if(g[a][b] > c){
                g[a][b] = g[b][a] = c ;
            }
        }

        dijkstra() ;

        cout << dist[n] << endl ;

    }
    return 0;
}

dijkstra使用堆优化，，使用stl中优先队列实现heap，，注意heap中结构体第一个存的是dist

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef pair<int,int> pii ;
const int N = 1e4 + 100 , M = 2 * N , T = 110;
int n,m ;
int h[N],e[M],w[M],ne[M] ,idx ;
int d[T] ;
bool st[T] ;

void add(int a,int b,int c){
    e[idx] = b , w[idx] = c ,ne[idx] = h[a] , h[a] = idx ++ ;
}

void dijkstra(){
    memset(d,0x3f,sizeof d) ;
    d[1] = 0 ;
    priority_queue<pii,vector<pii>,greater<pii> >  heap ;
    heap.push({0,1}) ;

    while(heap.size() ){
        pii item = heap.top() ;
        heap.pop() ;
        int b = item.second ,distance = item.first ;
        if(st[b]) continue ;
        st[b] = 1;
        for(int i = h[b] ; ~i ; i = ne[i] ){
            int j = e[i] ;
            if(d[j] > distance + w[i]){
                d[j] = distance + w[i] ;
                heap.push({d[j],j}) ;
            }
        }
    }

}
int main()
{
    while(scanf("%d %d",&n,&m) , n ){
        idx = 0 ;
        memset(h,-1,sizeof h) ;
        memset(st,0,sizeof st) ;

        for(int i = 0 ; i < m ; i++){
            int a ,b,c;
            scanf("%d %d %d",&a,&b,&c) ;
            add(a,b,c),add(b,a,c) ;
        }

        dijkstra() ;

        cout << d[n] << endl ;
    }

    return 0;
}

spfa正常写的spfa

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <stack>

using namespace std;

typedef pair<int,int> pii ;
const int N = 1e4 + 100 , M = 2 * N , T = 110;
int n,m ;
int h[N],e[M],w[M],ne[M] ,idx ;
int d[T] ;
bool st[T] ;

void add(int a,int b,int c){
    e[idx] = b , w[idx] = c ,ne[idx] = h[a] , h[a] = idx ++ ;
}

void spfa(){
    memset(d,0x3f,sizeof d) ;
    d[1] = 0 ;
    st[1] = 1 ;
    stack<int> s ;
    s.push(1) ;

    while(s.size()){
        int t = s.top() ;
        s.pop() ;
        st[t] =  0 ;

        for(int i = h[t] ;  ~i ; i = ne[i]){
            int j = e[i] ;
            if(d[j] > d[t] + w[i]){
                d[j] = d[t] + w[i] ;
                if(!st[j]){
                    st[j] = 1;
                    s.push(j) ;
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d %d",&n,&m) , n){
        idx = 0 ;
        memset(h,-1,sizeof h) ;
        memset(st,0,sizeof st) ;

        for(int i = 0  ;i < m; i++){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c) ;
            add(a,b,c) ,add(b,a,c) ;
        }

        spfa() ;

        cout << d[n] << endl ;
    }

    return 0;
}