题解 | #【模板】单源最短路2#

个人认为比较标准的邻接矩阵Dij写法，仅供参考

#include <bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;

int G[5050][5050];
int dis[5050];      //min dis from s to []
bool vis[5050] = {false};

void dij(int s, int n) {
    int i = 1, j = 1;
    fill(dis, dis + 5050, INF);
    dis[s] = 0;
    for (i = 1; i <= 5050; i++) {	//我服，是遍历所有5000个点不是n个，否则后面几组出问题
        int u = -1, MIN = INF;
        for (j = 1; j <= 5050; j++) {
            if (vis[j] == false && dis[j] < MIN) {
                u = j;
                MIN = dis[j];
            }
        }
        if (u == -1)   return;
        vis[u] = true;
        for (int v = 1; v <= 5050; v++) {
            if (vis[v] == false && G[u][v] != INF && dis[u] + G[u][v] < dis[v]) {
                dis[v] = dis[u] + G[u][v];
            }
        }
    }
}

int main() {
    int m, n;
    cin >> n >> m;
    fill(G[0], G[0] + 5050 * 5050, INF);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u][v] = w;
        G[v][u] = w;
    }
    dij(1, n);
    //for(int i=0;i<n;i++)    cout<<dis[i]<<" ";
    if (dis[n] != INF) cout << dis[n] << endl;
    else cout << "-1" << endl;
    system("pause");
    return 0;
}