适用范围

单源正权边最短路
时间复杂度O(n^2)

模板

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

using namespace std;

const int N = 510;

int d[N][N];        //两点之间的距离
int dist[N];        //点到1之间的距离
bool st[N];         //点是否为确定最短路点

int n,m;

int dj(){
    //将1点距离设置为0，其余点设置为无穷大
    memset(dist,0x3f,sizeof dist);

    dist[1] = 0;

    //将每一点最近的点最短路确立
    for(int i = 0;i < n;i ++){
        int t = -1;

        for(int j = 1;j <= n;j ++)
            if(!st[j] &&  (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for(int j = 1;j <= n;j ++)
            dist[j] = min(dist[j],dist[t] + d[t][j]);
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n]; 
}

int main(){
    cin >> n >> m;

    memset(d,0x3f,sizeof d);

    while(m --){
        int a,b,c;
        cin >> a >> b >> c;

        d[a][b] = min(d[a][b],c);
    }

    cout << dj();
}