社区讨论
为什么开了O2就会全RE?
P5960【模板】差分约束参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo918906
- 此快照首次捕获于
- 2023/10/28 03:54 2 年前
- 此快照最后确认于
- 2023/10/28 03:54 2 年前
CPP
#include<bits/stdc++.h>
#define ll long long
#define for1(i,a,b) for(int i=a;i<=b;i++)
const int inf=1e9;
using namespace std;
struct node{
int to;
int nex;
int w;
}a[500005];
int n,m,hd[500005],cnt,vis[500005],dis[500005],num[500005];//1表示在队列中
queue < int > dl;
node ru(int x,int y,int z)
{
a[++cnt].to=y;
a[cnt].w=z;
a[cnt].nex=hd[x];
hd[x]=cnt;
}
bool spfa()
{
while(!dl.empty())
{
int x=dl.front();
dl.pop();
vis[x]=0;
for(int i = hd[x];i;i=a[i].nex)
{
int y=a[i].to;
if(dis[y]>dis[x]+a[i].w)
{
dis[y]=dis[x]+a[i].w;
if(vis[y]==0)
{
vis[y]=1;
dl.push(y);
num[y]++;
if(num[y]>n+1) return 1;
}
}
}
}
return 0;
}
int main()
{
int x,y,z;
scanf("%d%d",&n,&m);
for1(i,1,m)
{
scanf("%d%d%d",&x,&y,&z);
ru(y,x,z);
}
for1(i,1,n) dis[i]=inf;
dis[1]=0;
for1(i,1,n)
{
dl.push(i);
num[i]++;
vis[i]=1;
}
if(spfa()==1) cout<<"NO"<<endl;
else
for1(i,1,n)
printf("%d ",dis[i]);
return 0;
}
考场上会出现这种情况吗?
回复
共 3 条回复,欢迎继续交流。
正在加载回复...