dijkstra算法最短路

冯泽代

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1001;
const int M = 10001;


struct edge {
    int v, w, next;
    edge(){}
    edge(int _v,int _w,int _next):v(_v),w(_w),next(_next){}
    /*edge(int _v, int _w, int _next) {
        v = _v;
        w = _w;
        next = _next;
    }*/
} e[M * 2];

int head[N], size;
int pre[N] = {0};
void init() {
    memset(head, -1, sizeof(head));
    size = 0;
}

void insert(int u, int v, int w) {
    e[size] = edge(v, w, head[u]);
    head[u] = size++;
}

void insert2(int u, int v, int w) {
    insert(u, v, w);
    insert(v, u, w);
}

int n, m;
int dis[N];
bool vis[N];
void dijkstra(int u) {
    memset(vis,false,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[u] = 0;
    for (int i = 0;i < n;++i) {
        int mind = 1000000000,minj = -1;
        for (int j = 1;j <= n;++j) {
            if (!vis[j] && dis[j] < mind) {
                minj = j;
                mind = dis[j];
                
            }
        }
        if (minj == -1) {
            return;
        }
        vis[minj] = true;
        for (int j = head[minj]; ~j; j = e[j].next) {
            int v = e[j].v;
            int w = e[j].w;
            if (!vis[v] && dis[v] > dis[minj] + w) {
                dis[v] = dis[minj] + w;
                pre[v] = minj;
            }
        }
    }
}
int main() {
    init();
    int u,v,w;
    cin >> n >> m;
    while(m--) {
        cin >> u >> v >> w;
        insert2(u,v,w);
    }
    dijkstra(1);
    cout << dis[n] << endl;
    for (int i = 0;i < n;i++) cout << pre[i] << " ";
    return 0;
}