用dijkstra算法求解
2025-07-30 19:45:13
发布于:浙江
9阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
int n,m,s;
struct node{
int to;
int w;
};
vector<vector<node> > a(1000001);
vector<int> dis(1000001,0x3f3f3f);
bool v[1000001]={0};
priority_queue<PII,vector<PII>,greater<PII> > q;
void dijkstra()
{
//memset(dis,,sizeof(dis));
q.push({0,s});
dis[s]=0;
while(!q.empty())
{
auto cur=q.top();
int nx=cur.second;
int nd=cur.first;
q.pop();
if(v[nx]) continue;
v[nx]=1;
for(int i=0;i<a[nx].size();i++)
{
int tox=a[nx][i].to;
int tow=a[nx][i].w;
if(dis[nx]+tow<dis[tox])
{
dis[tox]=dis[nx]+tow;
q.push({dis[tox],tox});
}
}
}
}
void print()
{
for(int i=1;i<=n;i++)
{
if(dis[i]!=0x3f3f3f) cout<<dis[i]<<" ";
else cout<<-1<<" ";
}
cout<<"\n";
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
a[x].push_back({y,z});
}
dijkstra();
print();
return 0;
}
全部评论 1
各位大佬不喜勿喷(
2025-07-30 来自 浙江
0
有帮助,赞一个