bzoj 2662 [BeiJing wc2012]冻结——分层图

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

这种的都是分层图。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=,M=;

int n,m,K,hd[N],xnt,dis[N][N],ans=0x3f3f3f3f;

bool vis[N][N];

struct Ed{

    int nxt,to,w;

    Ed(int n=,int t=,int w=):nxt(n),to(t),w(w) {}

}ed[M<<];

struct Node{

    int c,a,b;

    Node(int c=,int a=,int b=):c(c),a(a),b(b) {}

    bool operator< (const Node &b)const

    {return c>b.c;}

};

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

{

    ed[++xnt]=Ed(hd[x],y,z);hd[x]=xnt;

    ed[++xnt]=Ed(hd[y],x,z);hd[y]=xnt;

}

priority_queue<Node> q;

void dj()

{

    memset(dis,0x3f,sizeof dis);

    dis[][]=;

    q.push(Node(,,));

    while(q.size())

    {

        int a=q.top().a,b=q.top().b;q.pop();

        while(q.size()&&vis[a][b])a=q.top().a,b=q.top().b,q.pop();

        if(vis[a][b])break;vis[a][b]=;

        for(int i=hd[a],v;i;i=ed[i].nxt)

        {

            if(dis[v=ed[i].to][b]>dis[a][b]+ed[i].w)

                dis[v][b]=dis[a][b]+ed[i].w,q.push(Node(dis[v][b],v,b));

            if(b<K&&dis[v][b+]>dis[a][b]+(ed[i].w>>))

                dis[v][b+]=dis[a][b]+(ed[i].w>>),q.push(Node(dis[v][b+],v,b+));

        }

    }

}

int main()

{

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

    int x,y,z;

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

    {

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

        add(x,y,z);

    }

    dj();

    for(int i=;i<=K;i++)ans=min(ans,dis[n][i]);

    printf("%d\n",ans);

    return ;

}