题意描述

冻结

给定一张有 \(n\) 个点，\(m\) 条边的无向图，求 \(1\to n\) 之间的最短路。

当然，题目并没有那么简单，你还有 \(k\) 次机会，可以在当你通过某条路径时令路程减半。

其中使用这 \(k\) 个机会需要遵守以下三条规律：

1. 在一条道路上最多只能使用一次。（但在不同时刻可以重复使用在同一路径上）
2. 使用一次只在一条道路上起作用。
3. 你不必使用完所有的次数。

数据保证每条边的长度都是偶数。

最后，不知你是否发现了此题是水题

算法分析

发现数据范围感人：\(1\leq k\leq n\leq 50\)。

所以就可以用分层图乱搞了...。

利用 \(k+1\) 层图表示 \(k\) 次机会的使用状况，当你处于第 \(i(0\leq i\leq k)\) 层表示你用了 \(i\) 次机会。

考虑分层图最难的部分：建图。

同一层之间的节点都是最原始的题目数据连接。

在不同层时，假设第 \(i\) 层有边 \(u\to v\)，第 \(i+1\) 层有边 \(u‘\to v‘\)，边权为 \(w\)。（\(0\leq i<k\)）

那么连接 \(u\to v‘\) 和 \(v\to u‘\) 两条边，边权为 \(w/2\)。

然后从第 \(0\) 层的 \(1\) 号节点开始跑最短路，最终 \(ans=min_{0\leq i\leq k}\{dis(i,n)\}\)

也就是每一层的 \(n\) 号节点的最小值。

这里提到一个技巧适用于分层图中避免节点编号混淆问题：

令 \(id(x,y)\) 表示第 \(x\) 层的 \(y\) 号节点的编号，那么在本题中令 \(id(x,y)=x\times n+y\)。

那么想要得到任意节点的编号只要调用 \(id\) 函数即可。

然后就可以快乐的感受水题的洗礼了

代码实现

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#define N 100010
#define M 1000010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,k,head[N],cnt=0,dis[N];
bool vis[N];
struct Edge{
	int nxt,to,val;
}ed[M];

int read(){
	int x=0,f=1;char c=getchar();
	while(c<‘0‘ || c>‘9‘) f=(c==‘-‘)?-1:1,c=getchar();
	while(c>=‘0‘ && c<=‘9‘) x=x*10+c-48,c=getchar();
	return x*f;
}

int ID(int x,int y){return x*n+y;}

void add(int u,int v,int w){
	ed[++cnt].nxt=head[u];
	ed[cnt].to=v;
	ed[cnt].val=w;
	head[u]=cnt;
	return;
}

priority_queue<pair<int,int> >q;

void dij(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];i;i=ed[i].nxt){
			int v=ed[i].to,w=ed[i].val;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(-dis[v],v));
			}
		}
	}
	return;
}

int main(){
	n=read(),m=read(),k=read();
	int u,v,w;
	for(int i=1;i<=m;i++){
		u=read(),v=read(),w=read();
		for(int j=0;j<=k;j++) 
			add(ID(j,u),ID(j,v),w),add(ID(j,v),ID(j,u),w);
		for(int j=0;j<k;j++)
			add(ID(j,u),ID(j+1,v),w/2),add(ID(j,v),ID(j+1,u),w/2);
	}
	dij();
	int ans=INF;
	for(int i=0;i<=k;i++) ans=min(ans,dis[ID(i,n)]);
	printf("%d\n",ans);
	return 0;
}

完结撒花

P4822 [BJWC2012]冻结

原文：https://www.cnblogs.com/lpf-666/p/12739540.html