社区讨论
求助 全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 条回复,欢迎继续交流。
正在加载回复...