社区讨论

求助 全RE 但是本地编译可以运行

P4779【模板】单源最短路径(标准版)参与者 6已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@lobm0d0c
此快照首次捕获于
2023/10/29 23:11
2 年前
此快照最后确认于
2023/11/04 04:03
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int next,to,w;
}edge[100];
int cnt=0,n,m,tn,tt,tw,head[100],p[100],_min;
bool vis[100];
void add(int next,int t,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=t;
	edge[cnt].next=head[next];
	head[next]=cnt;
	cnt++;
}
void dij(int start)
{
	if(vis[start])return;
	vis[start]=true;
	_min=head[start];
	for(int i=head[start];i!=-1;i=edge[i].next)
	{
		if(edge[i].w<edge[_min].w)_min=i;
		p[edge[i].to]=p[edge[i].to]>p[start]+edge[i].w?p[start]+edge[i].w:p[edge[i].to];
	}
	dij(_min);
}
int main()
{
	memset(head,-1,sizeof(head));
	memset(vis,false,sizeof(vis));
	memset(p,0x3f,sizeof(p));
	cin>>n>>m>>tn;
	for(int i=0;i<m;i++)
	{
		cin>>tn>>tt>>tw;
		add(tn,tt,tw);
	}
	p[tn]=0;
	dij(tn);
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])dij(i);
	}
	for(int i=1;i<=n;i++)
	{
	    cout<<p[i]<<" ";
	}
	return 0;
}

回复

11 条回复,欢迎继续交流。

正在加载回复...