分层图【p4822】[BJWC2012]冻结

分层图的裸题.

把飞行路线稍微一改就过了.

把边权\(/2\)即可。

分层图的话,可以百度去搜的,讲这个的还是有不少.

注意,我们到达目的地不一定使用掉所有的\(SpellCard\)才能使\(ans\)最小。

因此

\[ans=min(ans,dis[n][i])
\]

还有数组要开大,一定要开大!

代码

#include<cstdio>

#include<queue>

#include<cstring>

#define R register

#define N 20008

using namespace std;

inline void in(int &x)

{

    int f=1;x=0;char s=getchar();

    while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();}

    while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();}

    x*=f;

}

int head[N],tot,n,m,s,t,k;

int dis[N][58],ans=2147483647;

bool vis[N][58];

struct cod{int u,v,w;}edge[N*6+8];

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

{

    edge[++tot].u=head[x];

    edge[tot].v=y;

    edge[tot].w=z;

    head[x]=tot;

}

struct coc{

    int u,d,used;

    bool operator <(const coc&a) const

    {

        return d>a.d;

    }

};

inline void dijkstra()

{

    memset(dis,127,sizeof dis);

    dis[s][0]=0;

    priority_queue<coc>q;

    q.push((coc){s,0,0});

    while(!q.empty())

    {

        int u=q.top().u,now=q.top().used;

        q.pop();

        if(vis[u][now])continue;

        vis[u][now]=true;

        for(R int i=head[u];i;i=edge[i].u)

        {

            if(now<k and !vis[edge[i].v][now+1] and dis[edge[i].v][now+1]>dis[u][now]+edge[i].w/2)

            {

                dis[edge[i].v][now+1]=dis[u][now]+edge[i].w/2;

                q.push((coc){edge[i].v,dis[edge[i].v][now+1],now+1});

            }

            if(!vis[edge[i].v][now] and dis[edge[i].v][now]>dis[u][now]+edge[i].w)

            {

                dis[edge[i].v][now]=dis[u][now]+edge[i].w;

                q.push((coc){edge[i].v,dis[edge[i].v][now],now});

            }

        }

    }

}

int main()

{

    in(n),in(m),in(k);s=1,t=n;

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

    {

        in(x),in(y),in(z);

        add(x,y,z);

        add(y,x,z);

    }

    dijkstra();

    for(R int i=0;i<=k;i++)

        ans=min(ans,dis[t][i]);

    printf("%d",ans);

}