CF1915G Bicycles 题解

分析

参照去年普及组 T4，很显然能发现就是一个暴力最短路。设 \(dis_{i,j}\) 表示从 \(1\) 走到 \(i\) 且能得到的 \(s\) 最小为 \(j\) 时的最短路。那么答案就是 \(\min\{dis_{n,i}|1 \le i \le V\}\)。

考虑最短路转移。对于当前的 \(dis_{u,j}\)，走到 \(v\) 的代价将会是 \(w_{u \to v} \times j\)。而在 \(v\) 这个点可以买下一辆自行车，所以是之后的 \(s\) 最小值为 \(\min(s_v,j)\)。即有：\(dis_{v,\min(s_v,j)}=\min(dis_{v,\min(s_v,j)},dis_{u,j})\)。

复杂度 \(O(nV\log n)\)

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define PII pair<int,pair<int,int>>
#define x first
#define y second
 
il int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
il void write(int x) {    
    if(x<0) putchar('-'),x=-x;    
    if(x>9) write(x/10);    
    putchar(x%10+'0');    
    return;    
}
 
const int N=2005;
int n,m,s[N];
int ne[N],e[N],h[N],w[N],idx;
int dis[N][N],vis[N][N];
 
il void add(int a,int b,int c){ne[++idx]=h[a],e[idx]=b,w[idx]=c,h[a]=idx;}
il void dij(){
	for(re int i=1;i<=n;++i)for(re int j=1;j<=1001;++j) dis[i][j]=1e16,vis[i][j]=0;
	priority_queue<PII,vector<PII>,greater<PII>> qu;
	qu.push({0,{s[1],1}}),dis[1][s[1]]=0;
	while(!qu.empty()){
		PII now=qu.top();qu.pop();
		if(vis[now.y.y][now.y.x]) continue;
		vis[now.y.y][now.y.x]=1;
		for(re int i=h[now.y.y];i;i=ne[i]){
			int j=e[i];if(dis[j][min(s[j],now.y.x)]>dis[now.y.y][now.y.x]+w[i]*now.y.x){
				dis[j][min(s[j],now.y.x)]=dis[now.y.y][now.y.x]+w[i]*now.y.x;
				qu.push({dis[j][min(s[j],now.y.x)],{min(s[j],now.y.x),j}});
			}
		}
	}
	return ;
}
 
il void solve(){
	n=read(),m=read();idx=0;
	for(re int i=1;i<=n;++i) h[i]=0;
	for(re int i=1,a,b,c;i<=m;++i)
		a=read(),b=read(),c=read(),add(a,b,c),add(b,a,c);
	for(re int i=1;i<=n;++i) s[i]=read();
	dij();int Min=1e18;
	for(re int i=1;i<=1001;++i) Min=min(Min,dis[n][i]);
	write(Min),puts("");
	return ;
}
 
signed main(){
	int t=read();while(t--)
	solve();
	return 0;
}