社区讨论
dij(链式前向星,堆优化)求助!
P3371【模板】单源最短路径(弱化版)参与者 4已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @lod14s6o
- 此快照首次捕获于
- 2023/10/30 23:03 2 年前
- 此快照最后确认于
- 2023/11/05 09:20 2 年前
C
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int max_n=100010;
const int max_m=500005;
int head[max_n],n,m,cnt=0,s,t,v[max_n],dis[max_n],k;//定义
struct node
{
int w,now;
inline bool operator <(const node &x)const
{
return w>x.w;
}
};
priority_queue<node>que;
struct book
{
int w;
int to;
int next;
} e[max_m];
void add(int u,int v,int wi)
{
e[++cnt].next=head[u];
e[cnt].to=v;
e[cnt].w=wi;
head[u]=cnt;
}
void djs(int s)
{
int u;
que.push((node){0,s});//入队
while(!que.empty())
{
node x=que.top();//取堆顶
que.pop();//删堆顶
u=x.now;//取起点
if(v[u]==1) continue;
else v[u]=1;
for(int i=head[u];i;i=e[i].next)//进行松弛操作
{
int vv=e[i].to;
if(dis[vv]>e[i].w+dis[u])
{
dis[vv]=e[i].w+dis[u];
if(v[vv]==0) que.push((node){dis[vv],vv});
}
}
}
}
int main()
{
cin>>n>>m>>s;//输入
memset (head,0,sizeof(head));//初始化各个端点的出度
memset (dis,0x7fffffff,sizeof(dis));//各点到s距离 初始化为int_max
memset (v,0,sizeof(v));//初始化个点,均未被访问
dis[s]=0;//s到s距离为零
for(int i=1;i<=m;i++) //输入各个边
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
djs(s);
for(int i=1;i<=n;i++) cout<<dis[i]<<" ";//欧凯
return 0;
}
大佬们,求助!
回复
共 6 条回复,欢迎继续交流。
正在加载回复...