注意到 $n\le 1000$，$T\le 200$，按照当前体力把图分成 $mxt$ 层，进行分层图最短路即可。

有几个要注意的地方：

• 一个点自己连边时，只需要连到他下一层。

• 当前点如果到了终点，直接输出。此时一定是最小的。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*y;
}
int n,m,nwt,mxt,t[1005];
struct node {
	int v,w,c;
};
vector<node>G[1005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int dis[2000005];
bool vis[2000005];
void dijkstra(int s) {
	memset(dis,0x3f,sizeof dis),dis[s]=0,q.push({0,s});
	while(!q.empty()) {
		int tmp=q.top().second,j=tmp/n,u=tmp%n;
		if(u==n-1) {
			cout<<dis[tmp];
			exit(0);
		}
		q.pop();
		if(vis[tmp])continue;
		vis[tmp]=1;
		if(j+1<=mxt&&dis[(j+1)*n+u]>dis[j*n+u]+t[u]) {
			dis[(j+1)*n+u]=dis[j*n+u]+t[u];
			q.push({dis[(j+1)*n+u],(j+1)*n+u});
		}
		for(auto p:G[u]) {
			int v=p.v,w=p.w,c=p.c;
			if(j<w) continue;
			if(dis[(j-w)*n+v]>dis[j*n+u]+c) {
				dis[(j-w)*n+v]=dis[j*n+u]+c;
				q.push({dis[(j-w)*n+v],(j-w)*n+v});
			}
		}
	}
}
signed main() {
//	freopen("travel.in","r",stdin);
	R(n),R(m),R(nwt),R(mxt);
	for(int i=0; i<n; ++i) R(t[i]);
	while(m--) {
		int R(u),R(v),R(w),R(c);
		G[u-1].push_back({v-1,w,c});
		G[v-1].push_back({u-1,w,c});
	}
	dijkstra(nwt*n);
	return 0;
}

最短路

正常状态d[i]：到i点所用最小时间。

本题多了体力，所以设置d[i][j]：到i点体力为j的最小时间

（每个点该休息多久？）

暴力，到一个点就for一下休息多久（体力不超出max）

code

bool M1;
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define look_memory cerr<<abs(&M1-&M2)/1024.0/1024<<"MB\n"

namespace syr
{
	const ll N = 1010;
	const ll M = 1e5+10;
	struct node {
		ll w; //所需体力 
		ll v; //所需时间 
		ll to;
		ll nxt;
	}e[2*M];
	struct node2 {
		ll x;
		ll w;
		ll v;
		friend bool operator < (node2 a, node2 b) {
			return a.v>b.v;
		}
	}tp;
	ll n, m, t, tmax, tot;
	ll a[N], h[N], v[N][N], dp[N][N];
	priority_queue <node2> q;
	void add (ll x, ll y, ll w, ll v) {
		e[++tot] = {w, v, y, h[x]};
		h[x] = tot;
	}
	void work()
	{
		cin>>n>>m>>t>>tmax;
		for (ll i=1; i<=n; i++) cin>>a[i];
		for (ll i=1; i<=m; i++) {
			ll x, y, w, v;
			cin>>x>>y>>w>>v;
			add(x, y, w, v);
			add(y, x, w, v);
		}
		memset(dp, 0x3f, sizeof(dp));
		dp[1][t] = 0;
		q.push({1, t, 0});
		while (!q.empty()) {
			tp = q.top();
			q.pop();
			if (v[tp.x][tp.w]) continue;
			v[tp.x][tp.w] = 1;
			if (tp.x==n) {
				cout<<tp.v;
				return;
			}
			for (ll i=1; i<=tmax-tp.w; i++) {
				ll w = tp.w+i, v = tp.v+i*a[tp.x];
				if (w>tmax) continue;
				if (dp[tp.x][w]>v) {
					dp[tp.x][w] = v;
					q.push({tp.x, w, v});
				}
			}
			for (ll i=h[tp.x]; i; i=e[i].nxt) {
				ll y = e[i].to;
				ll w = tp.w-e[i].w;
				ll v = tp.v+e[i].v;
				if (w<0) continue;
				if (dp[y][w]>v) {
					dp[y][w] = v;
					q.push({y, w, v});
				}
			}
		}
	}
}

bool M2;

int main()
{
//	freopen("a.in", "r", stdin);
	cin.tie(0)->sync_with_stdio(0);
	look_memory;
	syr::work();
	return 0;
}

直接分层图，然后注意每个点只需要连他下一层就行，连多了就T飞了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
bool Test_MLE_start;
constexpr int N=1e3+10,M=1e5+10,MAXT=205;
int _=1,n,m,T,maxT,tot=0,ans=2e9,head[N],tp[N],dis[N][MAXT];
bool vis[N][MAXT];struct edge{int v,w,x,nxt;}a[M<<1];
struct node{
	int u,val,t;
	friend bool operator <(const node A,const node B){return A.val>B.val;}
};priority_queue<node> q;
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("B.in","r",stdin);
//	freopen("std.out","w",stdout);
}inline void clr(){
//	Don't forget!

}void add(int u,int v,int w,int x){
	a[++tot].v=v,a[tot].w=w,a[tot].x=x;
	a[tot].nxt=head[u];
	head[u]=tot;
}void dijkstra(int u,int t){
	memset(dis,0x3f,sizeof(dis));
	dis[u][t]=0,q.push(node{u,0,t});
	while(!q.empty()){
		int u=q.top().u,t=q.top().t;q.pop();
		if(vis[u][t]) continue;vis[u][t]=1;
		if(u==n){
			printf("%d\n",dis[n][t]);
			exit(0);
		}
		if(t+1<=maxT&&dis[u][t+1]>dis[u][t]+tp[u]){
			dis[u][t+1]=dis[u][t]+tp[u];
			q.push(node{u,dis[u][t+1],t+1});
		}for(int i=head[u];i;i=a[i].nxt){
			int v=a[i].v,x=a[i].x;
			if(t<x) continue;
			if(dis[v][t-x]>dis[u][t]+a[i].w){
				dis[v][t-x]=dis[u][t]+a[i].w;
				q.push(node{v,dis[v][t-x],t-x});
			}
		}
	}
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads(),T=reads(),maxT=reads();
		for(int i=1;i<=n;i++) tp[i]=reads();
		for(int i=1;i<=m;i++){
			int u,v,w,x;u=reads(),v=reads(),x=reads(),w=reads();
			add(u,v,w,x),add(v,u,w,x);
		}dijkstra(1,T);
		for(int i=0;i<=maxT;i++) ans=min(ans,dis[n][i]);
		printf("%d\n",ans);
	}return 0;
}