害怕老师的小T 题解

题意

给定一个无向带权图，你可以将 $k$ 条长度为 $a_i$ 的路径上的边权设为 0，求从 1 到 $n$ 的最短路。

思路

前置知识：dijkstra，分层图，状压，dp

这题有人可能想到将最短路径存下来然后直接计算，但会被样例卡掉，所以正解应该是分层图。

想到了分层图，让我们来想想怎么分层。

如果将剩余老师消失器数量分层，那么我们无法判断 $a_i$。

可以发现本题中 $k$ 与 $a_i$ 较小，可以将他们一起分层，分别表示当前剩余的老师消失器状态和还可以免费走的路径数。（使用状压存老师消失器的状态）

但直接分层图容易TLE或MLE（不排除分层图有可能过的情况），所以我们可以只对 dis 数组和 vis 数组分层，就可以通过本题。

代码

#include<bits\stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,a[11];
struct N{
	int y;//当前到达的点
	ll v;//当前距离
	int k,c;//k:老师消失器使用状态,c:还剩多少免费路径
	bool operator<(const N &n1)const{
		return v>n1.v;
	}
}; 
vector<N> e[10001];
ll dis[10001][33][11];
bool vis[10001][33][11];
int main(){
	freopen("class.in","r",stdin);
	freopen("class.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,x,y,v;i<=m;i++){
		scanf("%d%d%d",&x,&y,&v);
		e[x].push_back({y,v,0,0});//邻接表存边
		e[y].push_back({x,v,0,0});
	}
	for(int i=1;i<=k;i++){
		scanf("%d",&a[i]);
	}
	memset(dis,0x3f,sizeof(dis));
	priority_queue<N> q;
	q.push({1,0,0,0});
	dis[1][0][0]=0;
	while(!q.empty()){//dijkstra
		N t=q.top();
		q.pop();
		if(vis[t.y][t.k][t.c])continue;
		vis[t.y][t.k][t.c]=1;
		for(N i:e[t.y]){
			if(t.c&&dis[i.y][t.k][t.c-1]>dis[t.y][t.k][t.c]){
      //如果当前还有剩余未使用免费路径
				dis[i.y][t.k][t.c-1]=dis[t.y][t.k][t.c];
				q.push({i.y,dis[i.y][t.k][t.c-1],t.k,t.c-1});
			}
			if(!t.c){//当前没有免费路径
				if(!t.c&&dis[i.y][t.k][t.c]>dis[t.y][t.k][t.c]+i.v){
        //不走免费路径
					dis[i.y][t.k][t.c]=dis[t.y][t.k][t.c]+i.v;
					q.push({i.y,dis[i.y][t.k][t.c],t.k,t.c});
				}
				for(int j=0;j<k;j++){
					if(!(t.k&(1<<j))){
          //走第j条免费路径
						if(dis[i.y][t.k+(1<<j)][a[j+1]+t.c-1]>dis[t.y][t.k][t.c]){
							dis[i.y][t.k+(1<<j)][a[j+1]+t.c-1]=dis[t.y][t.k][t.c];
							q.push({i.y,dis[i.y][t.k+(1<<j)][a[j+1]+t.c-1],t.k+(1<<j),a[j+1]+t.c-1});
						}
					}
				}
			}
		}
	}
	ll ans=1ll<<62;
	int mx=0;
	for(int i=1;i<=k;i++){
		mx=max(mx,a[i]);
	}
	for(int i=0;i<(1<<k);i++){
		for(int j=0;j<=mx;j++){
			ans=min(ans,dis[n][i][j]);//统计答案
		}
	}
	printf("%lld\n",ans);
	return 0;
}