[[BJWC2012] 冻结]

风丨铃 / 2024-07-17 / 原文

[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);//保持每层u和v的相连
			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);//第j层的u向第j+1层的v连接，就是使用了一次
			add(j*n+v,(j+1)*n+u,w/2);//同理j层v向j+1层u连接
		}
	}
	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;
}