学ACwing的写法

学ACwing的写法

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
//
// 这里是稀疏图 M 是 2e5 远小于 N * N
int h[N],e[M],ne[M],w[M],idx;
int n, m, s;
typedef pair<int,int> PII;
//
int dis[N];
bool vis[N];
void add(int a,int b,int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
// 朴素dijkstra
void dijkstra(int sx){
    dis[sx] = 0;
    // n - 1轮 选点
    for(int i = 1; i < n; i ++){
        int t = -1;// 表示 还未开始选
        for(int j = 1; j <= n; j ++){
            if(!vis[j] && (t == -1 || dis[j] < dis[t])) t = j;
        }
        // 根据选中的 t 更新 t可达的 其他点
        vis[t] = true;// 加入集合s
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            dis[j] = min(dis[j], dis[t] + w[i]);
        }
    }
}

void spfa(int sx){
    dis[sx] = 0;
    queue<int> q;
    q.push(sx);
    vis[sx] = true;
    while(q.size()){
        int t = q.front();
        q.pop();
        vis[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dis[j] > dis[t] + w[i]){
                dis[j] = dis[t] +w[i];
                if(!vis[j]){
                    q.push(j);
                    vis[j] = true;
                }
            }
        }
    }

}
// 堆优化 dijkstra
void dijkstrav2(int sx){
    priority_queue<PII,vector<PII>,greater<PII>> q;
    dis[sx] = 0;
    q.push({0,sx});
    while(q.size()){
        auto item = q.top();
        q.pop();
        int t = item.second;
        if(vis[t] == true) continue;
        vis[t] = true;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dis[j] > dis[t] + w[i]){
                dis[j] = dis[t] + w[i];
                q.push({dis[j],j});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(h, -1,sizeof h);
    memset(dis, 0x3f,sizeof dis);
    cin >> n >> m >> s;
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
//    dijkstra(1);
    dijkstrav2(s);
    for(int i = 1; i <= n; i ++)
        cout << dis[i] << " ";
    return 0;
}