社区讨论

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 条回复,欢迎继续交流。

正在加载回复...