dijkstra + 单调栈优化

打 Div.3 发现两个最短路板子题一个用的 SPFA 一个用的邻接矩阵，赶紧补个。

#include <iostream>
#include <queue>
#define MAXN 20010
using namespace std;
const int inf = 2147483647;
int n,m,s,t,cnt;
int dis[MAXN],h[MAXN],to[MAXN],val[MAXN],nxt[MAXN];
bool vis[MAXN];
struct node {
    int v,w;
    friend bool operator < (node a,node b) {
        return a.w > b.w;
    }
} tmp;
priority_queue <node> q;
void add(int a,int b,int c) {
    to[++cnt] = b;
    val[cnt] = c;
    nxt[cnt] = h[a];
    h[a] = cnt;
}
void dijkstra() {
    for(int i = 1;i <= n;++ i) dis[i] = inf;
    dis[s] = 0;
    tmp.v = s;tmp.w = 0;q.push(tmp);
    while(!q.empty()) {
        int u = q.top().v;
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = h[u];i;i = nxt[i]) {
            if(dis[to[i]] > (long long)dis[u] + val[i]) {
                dis[to[i]] = dis[u] + val[i];
                tmp.w = dis[to[i]];
                tmp.v = to[i];
                q.push(tmp);
            }
        }
    }
    for(int i = 1;i <= n;++i)
    cout <<dis[i] << ' ';
}
int main() {
    cin >> n >> m >> s;
    int u,v,w;
    for(int i = 1;i <= m;++ i) {
        cin >> u >> v >> w;
        add(u,v,w);
    }
    dijkstra();
    return 0;
}

时间复杂度\({O(nlogn)}\)