这到底是堆优 Dijkstra 还是堆优 SPFA?
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 100010
int n,m,s,dis[MAXN];
struct edge{
int v,w;
bool operator>(const edge &tmp)const{
return w > tmp.w;
}
};
basic_string<edge> p[MAXN];
priority_queue<edge,basic_string<edge>,greater<edge> > q;
void Dijkstra(){
fill(dis,dis + n + 1,INT_MAX);
q.push({s,dis[s] = 0});
while(!q.empty()){
int u = q.top().v,d = q.top().w;
q.pop();
if(d != dis[u]) continue;
for(const auto &[v,w] : p[u]){
if(dis[v] > LL(dis[u]) + w){
dis[v] = dis[u] + w;
q.push({v,dis[v]});
}
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("P4779.in","r",stdin);
#endif
cin.tie(0) -> ios::sync_with_stdio(0);
cout.tie(0);
cin>>n>>m>>s;
for(int i = 1,u,v,w;i <= m;i++){
cin>>u>>v>>w;
p[u].push_back({v,w});
}
Dijkstra();
for(int i = 1;i <= n;i++){
cout<<dis[i]<<' ';
}
return 0;
}