bzoj 2662: [BeiJing wc2012]冻结

.

最短路。
难得水题。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

int n,m,k,fst[60],num=0,dis[60][60],v[60],ans=2147483647;
struct edge
{
    int x,y,c,n;
}e[2010];

void ins(int x,int y,int c)
{
    e[++num]={x,y,c,fst[x]};
    fst[x]=num;
}
int main()
{
    memset(dis,63,sizeof(dis));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        ins(x,y,c);
        ins(y,x,c);
    }
    queue<int>q;
    q.push(1);
    v[1]=1;
    dis[0][1]=0;
    while(!q.empty())
    {
        int x=q.front();
        v[x]=0;
        for(int i=fst[x];i;i=e[i].n)
        {
            int y=e[i].y;
            for(int j=0;j<=k;j++)
            {
                if(dis[j][y]>dis[j][x]+e[i].c)
                {
                    dis[j][y]=dis[j][x]+e[i].c;
                    if(!v[y])
                    {
                        v[y]=1;
                        q.push(y);
                    }
                }
            }
            for(int j=0;j<k;j++)
            {
                if(dis[j+1][y]>dis[j][x]+(e[i].c>>1))
                {
                    dis[j+1][y]=dis[j][x]+(e[i].c>>1);
                    if(!v[y])
                    {
                        v[y]=1;
                        q.push(y);
                    }
                }
            }
        }
        q.pop();
    }
    for(int i=0;i<=k;i++)
    ans=min(ans,dis[i][n]);
    printf("%d\n",ans);
}