903. 昂贵的聘礼(acwing)

单源最短路

903. 昂贵的聘礼

题目大意：

要拿到点i的物品需要vali的价值。但是点i会在已经拿到点j物品的时候打折。而且每个点都有一个地位，地位差直接或者间接超过m的不能交易。问拿到点1物品的最小花费。

思路和代码：

我一开始想处理路径差值的方法是这样的：
$$
abs(rnk_i - rnk_1)<=m
$$
但是错就错在这里，用绝对值的话，路径上可能有两个点的地位差值最坏是2*m。所以还是需要去枚举长度为m的地位区间。

我的思路是从点1出发，求出到点i的最短花费。

ll n , m , k ; 

struct edge{
	ll to , len ;
};

vct eg[110] ;
ll val[110] , rnk[110] ;

ll spfa(ll dw , ll up){
	
	vct ds(n + 1 , INF) ;
	vct inq(n + 1 , 0) ;
	inq[1] = 1 ;
	ds[1] = val[1] ;
	queue q ;
	q.push(1) ;
	while(q.size()){
		
		ll idx = q.front() ;
		q.pop() ;
		inq[idx] = 0 ;
		for(auto x : eg[idx]){
			if(rnk[x.to] < dw || up < rnk[x.to]) continue ;
			ll ifgoto = ds[idx] + x.len + val[x.to] - val[idx] ;
			if(ds[x.to] > ifgoto){
				ds[x.to] = ifgoto ;
				if(inq[x.to]) continue ;
				q.push(x.to) ;
				inq[x.to] = 1 ;
			}
		}
	}
	
	ll ans = INF ;
	rep(i , 1 , n)
	if(abs(rnk[i] - rnk[1]) <= m)
	ans = min(ans , ds[i]) ;
	return ans ;
	
}

void solve(){
	
	cin >> m >> n ;
	
	rep(i , 1 , n){
		ll num ;
		cin >> val[i] >> rnk[i] >> num ;
		
		rep(j , 1 , num){
			ll to , prs ;
			cin >> to >> prs ;
			//if(abs(rnk[i] - rnk[1]) > m) continue ;
			eg[i].pb({to , prs}) ;
			//eg[to].pb({i , prs}) ;
		}
	}
	
	ll ans = INF ;
	rep(i , rnk[1] - m , rnk[1]) ans = min(ans , spfa(i , i + m)) ;
	cout << ans << "\n" ;
	
}//code_by_tyrii 

再就是官方的题解：

有两个要点：反向建图+超级源点

先将所有点和点0链接起来，边权就是点i的权值。再以点0为起点做其他所有点的最短路。

ll n , m , k ; 
ll val[N] , rnk[N] ;

struct edge{
	ll to , len ;
};

vct eg[N] ;

ll dij(ll dw , ll up){
	
	vct ds(n + 1 , INF) ;
	vct vis(n + 1 , 0) ;
	ds[0] = 0 ;
	
	rep(i , 1 , n){
		ll now = -1 ;
		rep(j , 0 , n)
			if(!vis[j] && (now == -1 || ds[j] < ds[now])) now = j ;
        
		vis[now] = 1 ;
		
		for(auto x : eg[now]) {
			if(rnk[x.to] > up || rnk[x.to] < dw) continue ;
			ds[x.to] = min(ds[x.to] , ds[now] + x.len) ;
		}
	}
	return ds[1] ;
}

void solve(){
	cin >> m >> n ;
	
	rep(i , 1 , n){
		ll num ;
		cin >> val[i] >> rnk[i] >> num ;
		eg[0].pb({i , val[i]}) ;//超级源点
		while(num -- ){
			ll u , w ;
			cin >> u >> w ;
			eg[u].pb({i , w}) ;//反向建图
		}
	}
	
	ll ans = INF ;
	rep(i , rnk[1] - m , rnk[1])
		ans = min(ans , dij(i , i + m)) ;
	cout << ans << "\n" ;
	
}//code_by_tyrii 

小结：

这题如果反向建图，则要把所有点到点1的最短路求出来（多源最短路？）。设置一个超级源点0可以将其变成一个单源最短路的问题。