打 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)}\)