最短路

正常状态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;
}