bzoj2763 [JLOI2011]飞行路线——分层图

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2763

构建分层图。

代码如下：

写法1(空间略大)(时间很慢)：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

priority_queue<pair<int,int> >q;

int const maxn=2e5+,maxm=;

int n,m,k,s,t,head[maxn],ct,dis[maxn];

bool vis[maxn];

struct N{

    int to,next,w;

    N(int t=,int n=,int w=):to(t),next(n),w(w) {}

}edge[maxm<<];

void add(int x,int y,int z)

{

    edge[++ct]=N(y,head[x],z); head[x]=ct;

    edge[++ct]=N(x,head[y],z); head[y]=ct;

    for(int i=;i<=k-;i++)

    {

        int u=x+i*n,v=y+(i+)*n;

        edge[++ct]=N(v,head[u],); head[u]=ct;

        u=y+i*n,v=x+(i+)*n;

        edge[++ct]=N(v,head[u],); head[u]=ct;

        u=x+(i+)*n,v=y+(i+)*n;

        edge[++ct]=N(v,head[u],z); head[u]=ct;

        edge[++ct]=N(u,head[v],z); head[v]=ct;

    }

}

void dijkstra()

{

    memset(dis,0x3f,sizeof dis);

    dis[s]=; q.push(make_pair(,s));

    while(q.size())

    {

        int x=q.top().second; q.pop();

        while(vis[x]&&q.size())x=q.top().second,q.pop();

        if(vis[x])break; vis[x]=;

        for(int i=head[x];i;i=edge[i].next)

        {

            int u=edge[i].to;

            if(dis[u]>dis[x]+edge[i].w)

            {

                dis[u]=dis[x]+edge[i].w;

                q.push(make_pair(-dis[u],u));

            }

        }

    }

}

int main()

{

    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);

    t+=k*n;

    for(int i=,x,y,z;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

    }

    dijkstra();

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

    return ;

}

写法2(空间小)(时间飞快)(bfs)(dijkstra?)：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int const maxn=,maxm=;

struct P{

    int bh,d,f;

    P(int b=,int d=,int f=):bh(b),d(d),f(f) {}

    bool operator < (const P &y) const

    {

        return d>y.d;//priority_queue 是从大到小排序

    }

};

priority_queue<P>q;

int n,m,K,head[maxn],ct,s,t,dis[maxn][];

bool vis[maxn][];

struct N{

    int to,next,w;

    N(int t=,int n=,int w=):to(t),next(n),w(w) {}

}edge[maxm<<];

void add(int x,int y,int z){edge[++ct]=N(y,head[x],z); head[x]=ct;}

void bfs()

{

    memset(dis,0x3f,sizeof dis);

    dis[s][]=; q.push(P(s,,));

    while(q.size())

    {

        int x=q.top().bh, d=q.top().d, f=q.top().f; q.pop();

        if(vis[x][f])continue;

        vis[x][f]=;

        if(x==t)

        {

            printf("%d",d); return;

        }

        for(int i=head[x];i;i=edge[i].next)

        {

            int u=edge[i].to;

            if(f<K&&dis[u][f+]>d&&!vis[u][f+])

            {

                dis[u][f+]=d;

                q.push(P(u,d,f+));

            }

            if(dis[u][f]>d+edge[i].w&&!vis[u][f])

            {

                dis[u][f]=d+edge[i].w;

                q.push(P(u,dis[u][f],f));

            }

        }

    }

}

int main()

{

    scanf("%d%d%d%d%d",&n,&m,&K,&s,&t);

    for(int i=,x,y,z;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

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

    }

    bfs();

    return ;

}