bzoj 2763: [JLOI2011]飞行路线【分层图+spfa】

为什么早年的题总是从0开始标号啊……又zz了一次WA

分层图的题只有这一个套路吧，建分层图，然后优化时间是分层跑spfa然后层与层之间单独跑即可

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int N=50005,inf=1e9;

int n,m,k,s,t,h[N],cnt,dis[N],d[N];

bool v[N];

deque<int>q;

struct qwe

{

    int ne,no,to,va;

}e[N<<2];

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

inline void add(int u,int v,int w)

{

    cnt++;

    e[cnt].ne=h[u];

    e[cnt].no=u;

    e[cnt].to=v;

    e[cnt].va=w;

    h[u]=cnt;

}

void spfa()

{

    while(!q.empty())

    {

        int u=q.front();

        q.pop_front();

        v[u]=0;

        for(int i=h[u];i;i=e[i].ne)

            if(dis[e[i].to]>dis[u]+e[i].va)

            {

                dis[e[i].to]=dis[u]+e[i].va;

                if(!v[e[i].to])

                {

                    v[e[i].to]=1;

                    if(!q.empty()&&dis[q.front()]>dis[e[i].to])

                        q.push_front(e[i].to);

                    else

                        q.push_back(e[i].to);

                }

            }

    }

}

int main()

{

    n=read(),m=read(),k=read(),s=read()+1,t=read()+1;

    for(int i=1;i<=m;i++)

    {

        int x=read()+1,y=read()+1,z=read();

        add(x,y,z),add(y,x,z);

    }

    for(int i=1;i<=n;i++)

        dis[i]=inf;

    v[s]=1,dis[s]=0,q.push_back(s);

    spfa();

    for(int con=1;con<=k;con++)

    {

        for(int i=1;i<=n;i++)

            d[i]=inf;

        v[s]=1,dis[s]=0,q.push_back(s);

        for(int i=1;i<=cnt;i++)

            if(d[e[i].to]>dis[e[i].no])

            {

                d[e[i].to]=dis[e[i].no];

                if(!v[e[i].to])

                {

                    v[e[i].to]=1;

                    if(!q.empty()&&d[q.front()]>d[e[i].to])

                        q.push_front(e[i].to);

                    else

                        q.push_back(e[i].to);

                }

            }

        for(int i=1;i<=n;i++)

            dis[i]=d[i];

        spfa();

    }

    printf("%d\n",dis[t]);

    return 0;

}

巴特西

bzoj 2763: [JLOI2011]飞行路线【分层图+spfa】

最新文章

热门文章