社区讨论

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

正在加载回复...