社区讨论
自己测ac,评测机re????????
P2296[NOIP 2014 提高组] 寻找道路参与者 10已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @mi4ep36l
- 此快照首次捕获于
- 2025/11/18 18:04 4 个月前
- 此快照最后确认于
- 2025/11/18 18:04 4 个月前
'''c++
CPP#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#define M 500000
using namespace std;
int n,m;
struct E
{
int to,next,w;
}e[M];
int tope,head[M];
int ae(int x,int y,int z)
{
tope++;e[tope].next=head[x];e[tope].to=y;e[tope].w=z;head[x]=tope;
}
E e1[M];
int tope1,head1[M];
int ae1(int x,int y,int z)
{
tope1++;e1[tope1].next=head1[x];e1[tope1].to=y;e1[tope1].w=z;head1[x]=tope1;
}
int dis[M],isinque[M];
queue<int>pig;
int spfa(int x)
{
for(int i=1;i<=n;++i)
dis[i]=1e7;
dis[x]=0;isinque[x]=1;pig.push(x);
int ce;
do
{
ce=pig.front();
isinque[ce]=0;
pig.pop();
for(int i=head[ce];i;i=e[i].next)
{
if(dis[ce]+e[i].w<dis[e[i].to])
{
dis[e[i].to]=dis[ce]+e[i].w;
if(isinque[e[i].to]==0)
{
pig.push(e[i].to);
isinque[e[i].to]=1;
}
}
}
}while(!pig.empty());
}
int dis1[M],isinque1[M];
queue<int>pig1;
int spfa1(int x)
{
for(int i=1;i<=n;++i)
dis1[i]=1e7;
dis1[x]=0;
isinque1[x]=1;
pig1.push(x);
int ce;
do
{
ce=pig1.front();
isinque1[ce]=0;
pig1.pop();
for(int i=head1[ce];i;i=e1[i].next)
{
if(dis1[ce]+e1[i].w<dis1[e1[i].to])
{
dis1[e1[i].to]=dis1[ce]+e1[i].w;
if(isinque1[e1[i].to]==0)
{
pig1.push(e1[i].to);
isinque1[e1[i].to]=1;
}
}
}
}while(!pig1.empty());
}
int main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
scanf("%d%d",&n,&m);
int ta,tb,st,ed;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&ta,&tb);
ae1(tb,ta,1);
ae(ta,tb,1);
}
scanf("%d%d",&st,&ed);
spfa1(ed);
for(int i=1;i<=n;++i)
{
if(dis1[i]==1e7)
{
for(int x=head1[i];x;x=e1[x].next)
{
isinque[e1[x].to]=1;
}
}
}
spfa(st);
printf("%d\n",dis[ed]);
return 0;
}
CPP回复
共 9 条回复,欢迎继续交流。
正在加载回复...