[BJWC2012] 冻结

题目大意

在能有\(k\)次机会使得某些道路变为其\(\frac{1}{2}\)长度的情况下，求\(1\)到\(n\)的最短路

做法

其实就是分层最短路的模板题，有\(k\)次机会减少，那么对于一个点来说就有可能是在这前使用了\(0\)~\(k\)次减少的机会到达的，每个点都有\(k\)个分身，故要建\(k+1\)个层，建好之后直接跑最短路，最后"\(n\)"点有\(k+1\)个，要遍历\(n\)及它的\(k\)个分身就能得到答案

注意

每个点相当于变成了\(k+1\)个点，那么关于结点个数的数组至少要开到\(50×51=2050\)，边个数的数组要开到\(1000×(50×2+51×2)=202000\)

洛谷P4822

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 3005;
int n,m,k,dis[maxn];
int cnt,head[maxn];
bool vis[maxn];
struct Edge{
	int to,len,next;
}edge[202001];
struct node{
	int id,dist;
	bool operator < (const node &x) const
	{
		return dist > x.dist;
	}
};
priority_queue <node> q;

inline void add(int u,int v,int w)
{
	cnt ++;
	edge[cnt].to = v;
	edge[cnt].len = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
	return ;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		for(int j=0;j<=k;j++)
		{
			add(j*n+u,j*n+v,w);
			add(j*n+v,j*n+u,w);
		} 
        for(int j=0;j<k;j++)
        {
        	add(j*n+u,(j+1)*n+v,w/2);
			add(j*n+v,(j+1)*n+u,w/2);
		}
	}
	memset(dis,127,sizeof(dis));
	dis[1] = 0;q.push((node){1,0});
	while(!q.empty())
	{
		node M = q.top(); q.pop();
		int u = M.id;
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i=head[u];i;i=edge[i].next)
		{
			int v = edge[i].to;
			if(dis[v] > dis[u] + edge[i].len)
			{
				dis[v] = dis[u] + edge[i].len;
				q.push((node){v,dis[v]});
			}
		}
	}
	int ans = 2147483647;
	for(int i=k;i>=0;i--)
		ans = min(ans,dis[i*n+n]);
	printf("%d",ans);
	return 0;
}