题目链接：BZOJ2662-BeijingWC2012-冻结

题意：

给一个无向图带权图，然后有k次机会，每次可以将一条边的边权变为一半，问从1出发到n的最短路。

题解：

分层图。

解法一：暴力建图，建一个n*k个点的图，每层内部边相同，层与层之间用权值为w/2的边相连。跑dijkstra即可。

解法二：跑k次dijkstra，每次结束后用新数组f记录上一次的dis，然后枚举边进行转移。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
const int MAXM=1009;
const int inf=0x3f3f3f3f;
int n,m,k;
struct EDGE
{
    int v,w,nxt;
} edge[MAXM*2];
int cnt=0,fir[MAXN];
void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
struct node
{
    int u;
    int d;
    node(int u,int d):u(u),d(d) {}
    bool operator < (const node &a) const
    {
        return d>a.d;
    }
};
bool used[MAXN];
int dis[MAXN],f[MAXN];
void dijkstra(int st)
{
    priority_queue<node> que;
    while(!que.empty())
        que.pop();
    for(int i=1; i<=n; i++)
        que.push(node(i,dis[i]));
    memset(used,0,sizeof(used));
    while(!que.empty())
    {
        int u=que.top().u;
        que.pop();
        if(used[u])
            continue;
        used[u]=1;
        for(int i=fir[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(used[v])
                continue;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                que.push(node(v,dis[v]));
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    memset(fir,-1,sizeof(fir));
    for(int i=1; i<=m; i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    dis[1]=0;
    dijkstra(1);
    while(k--)
    {
        for(int i=1; i<=n; i++)
            f[i]=dis[i];
        for(int u=1; u<=n; u++)
        {
            for(int i=fir[u]; i!=-1; i=edge[i].nxt)
            {
                int v=edge[i].v;
                int w=edge[i].w;
                w/=2;
                dis[v]=min(dis[v],f[u]+w);
            }
        }
        dijkstra(1);
    }
    printf("%d\n",dis[n]);
    return 0;
}