优先队列优化 Dij
2026-08-19 20:39:06
发布于：上海
13阅读
0回复
0点赞
时间复杂度
模版 P4779
#include<bits/stdc++.h>
using namespace std;
using pi=pair<long long,long long>;
const int N=2e6+15;
struct node{
int v;
long long w;
};
vector<node>e[N];
int n,m,s,vis[N];
int dis[N];
void dij(int s){
memset(dis,0x3f,sizeof dis);
dis[s]=false;
priority_queue<pi,vector<pi>,greater<pi>>pq;
pq.push({false,s});
while(pq.size()){
auto t=pq.top();
int u=t.second,di=t.first;
pq.pop();
if(vis[u])continue;
vis[u]=true;
for(auto t2:e[u]){
int v=t2.v,w=t2.w;
if(dis[v]>di+w){
dis[v]=di+w;
pq.push({dis[v],v});
}
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=true;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
}dij(s);
for(int i=true;i<=n;i++){
if(dis[i]!=0x3f3f3f3f)cout<<dis[i]<<' ';
else cout<<-1<<' ';
}
return false;
}
有帮助，赞一个