题面：

有n个城市，编号0至n-1。每个城市都有且仅有一个加油站，每个加油站都能提供无限多的汽油，第i个加油站的油价是p[i]元每升。你汽车的油箱容量是tank升，一开始汽车油箱没有汽油，你要从0号城市出发，目标是到达1号城市。城市之间总共有m条双向道路，例如:u,v,w，表示城市u和城市v之间有一条双向道路，行使这条道路要消耗w升汽油。注意：你要保证汽车行使在道路过程中不能因为油箱的汽油不够而抛锚，那是不容许的，因为只有在城市才有加油站，在道路中途是没有加油站的。输出你能完成任务的最小费用，如果不可能完成任务，输出-1。

思路：

首先，最simple的做法是跑dp（忽略爆搜）。我们记f[i][j]为当前在i节点，然后目前有j升汽油时最小的费用。首先我们忽略空间复杂度（50 * 1000000 * 8字节显然过不了256M）。

我们考虑转移，我们用类似于最短路dijkstra的方法进行转移（就是把每个状态看作一个点），对于每个状态f[i][j]，枚举下一个点v,以及到那里时的汽油k，通过f[i][j]转移到f[v][k].

具体转移如下(G[i][j]表示i,j之间的路程)

当p[i]<p[v]:

f[v][k]=min(f[i][j]+(k+G[i][v]-j)*p[i]); (k+G[i][v]<=tank)//也就是在当前节点买够再出发。
f[v][k]=min(f[i][j]+(tank-j)*p[i]+(G[i][v]+k-tank)*p[v]);(k+G[i][v]>tank)//因油箱容量不足，所以买满再出发，到目的地再买到k

当p[i]>=p[v]：

f[v][k]=min(f[i][j]+(G[i][v]-j)*p[i]+k*p[v]); (G[i][v]>j)//当前点油不够，当前点买够路上的油，到了再买。
f[v][k]=min(f[i][j]+(k+G[i][v]-j)*p[v]); (G[i][v]<=j)//当前点油足够，直接过去再买。

好，现在我们来算算时间复杂度。

枚举i,j,v,k,完了，O（50* 1000000 * 50 * 1000000），人生苦短。

优化：

我们考虑瓶颈在何处，瓶颈显然是油箱容量和边长度太大了，明显正解时间复杂度与此无关。

其实呢，我们发现我们记录的j很多状态是无用的，比如对于某个节点i，它到终点的距离是100，那么我们f[i][101]显然是没用的。

我们考虑哪些是有用的，易发现我们j只用记录O(n)个，分别是i到其它点的距离。（当然0和tank也要记录）

证明如下：

比如我们要求i到v要花费的最少钱，我们考虑中转点k

如果我们中转点不买油，显然我们i到v走最短路最优，然后要记录的容量正好是i到v的距离。

否则，如果要在k买油，那么k买油一定是比在i买油更优的，我们可以考虑先从i转移到k，再从k转移到v。

那么做法便显然了。

用f[i][j]记录当前再点i,有G[i][j]那么多的汽油的最小花费。

然后就同上面类似的转移就行了。

时间复杂度把两个1e6优化成了两个50，时间复杂度O(n^4)

可以通过本题。

代码：

#include<bits/stdc++.h>
#define int long long 

using namespace std;
int n,m,tank;
int p[55];
int G[55][55];
long long f[55][55];
vector<int> son[55];
bool pd[55][55];
struct data{
	int u;
	int now;
	bool operator < (data const &A) const
	{return (u<A.u);};
};
signed main(){
	scanf("%lld%lld%lld",&n,&m,&tank);
	for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			G[i][j]=1e9;
	for(int i=1;i<=n;i++)
		G[i][n+1]=tank;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		u++,v++;
		G[u][v]=min(G[u][v],w);
		G[v][u]=min(G[v][u],w);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
	if(G[1][2]==1e9){
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++){
		priority_queue<pair<int,int> >q;
		while(!q.empty())q.pop();
		for(int j=1;j<=n;j++)
			if(i!=j&&G[i][j]!=1e9&&G[i][j]<=tank)q.push(make_pair(-G[i][j],j));
		son[i].push_back(0);
		while(!q.empty()){
			son[i].push_back(q.top().second);
			q.pop();
		}
		son[i].push_back(n+1);
	}
	priority_queue<pair<long long,data> >q;
	while(!q.empty())q.pop();
	memset(f,127,sizeof(f));
	for(int i=0;i<son[1].size();i++)
		f[1][i]=G[1][son[1][i]]*p[1],q.push(make_pair(-f[1][i],(data){1,i}));
	while(!q.empty()){
		data U=q.top().second;
		q.pop();
		if(pd[U.u][U.now])continue;
		pd[U.u][U.now]=true;
		for(int i=1;i<=n;i++){
			if(G[U.u][i]>tank)continue;
			if(U.u==i){
				for(int j=U.now+1;j<son[U.u].size();j++){
					if(f[U.u][U.now]+(G[U.u][son[U.u][j]]-G[U.u][son[U.u][U.now]])*p[U.u]<f[U.u][j]){
						f[U.u][j]=f[U.u][U.now]+(G[U.u][son[U.u][j]]-G[U.u][son[U.u][U.now]])*p[U.u];
						q.push(make_pair(-f[U.u][j],(data){U.u,j}));
					}
				}
			}
			else{
				if(p[U.u]<p[i]){
					for(int j=0;j<son[i].size();j++){
						if(G[i][son[i][j]]+G[U.u][i]<G[U.u][son[U.u][U.now]])continue;
						if(G[i][son[i][j]]+G[U.u][i]>tank){
							int ned1=tank-G[U.u][son[U.u][U.now]];
							int ned2=G[i][son[i][j]]-(tank-G[U.u][i]);
							if(f[U.u][U.now]+ned1*p[U.u]+ned2*p[i]<f[i][j]){
								f[i][j]=f[U.u][U.now]+ned1*p[U.u]+ned2*p[i];
								q.push(make_pair(-f[i][j],(data){i,j}));
							}
						}else{
							int ned=G[U.u][i]+G[i][son[i][j]]-G[U.u][son[U.u][U.now]];
							if(f[U.u][U.now]+ned*p[U.u]<f[i][j]){
								f[i][j]=f[U.u][U.now]+ned*p[U.u];
								q.push(make_pair(-f[i][j],(data){i,j}) );
							}
						}
					}
				}
				else{
					for(int j=0;j<son[i].size();j++){
						if(G[i][son[i][j]]+G[U.u][i]<G[U.u][son[U.u][U.now]])continue;
					if(G[U.u][son[U.u][U.now]]<G[U.u][i]){
						int ned1=G[U.u][i]-G[U.u][son[U.u][U.now]];
						int ned2=G[i][son[i][j]];
						if(f[U.u][U.now]+ned1*p[U.u]+ned2*p[i]<f[i][j]){
							f[i][j]=f[U.u][U.now]+ned1*p[U.u]+ned2*p[i];
							q.push(make_pair(-f[i][j],(data){i,j}));
						}
					}else{
						int ned=G[i][son[i][j]]-G[U.u][son[U.u][U.now]]+G[U.u][i];
						if(f[U.u][U.now]+ned*p[i]<f[i][j]){
							f[i][j]=f[U.u][U.now]+ned*p[i];
							q.push(make_pair(-f[i][j],(data){i,j}));
						}
					}
				}
				}
			}
		}
	}
	long long ans=1e15;
	for(int i=0;i<son[2].size();i++){
		ans=min(ans,f[2][i]);
	}
	printf("%lld\n",ans);
	return 0;
}