题目链接: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;
}