题目链接：https://codeforc.es/gym/101933/problem/D
题意：地图上有 n 个位置和 m 条边，每条边连接 u、v 且有一个距离 w，一共有 k 个询问，每个询问表示 ti 时间在位置 ui 有人下单点了披萨，而披萨店在 di 时间做好披萨可以送出去，披萨店在位置 1，送披萨必须按顺序送，问客人从下单到拿到披萨的最长等待时间最短是多少。
题解：首先可以对每个点跑一次 dij，预处理出每两点之间的最短路，然后考虑二分答案，判断是否合法。dp[i][j]代表已经送完前 i 个位置，且拿了前 j 个位置的披萨的最小时间，还需要一维 k，0 表示送完以后当前在第 i 个点披萨的位置，1 表示当前在披萨店，然后进行转移即可。
#include <bits/stdc++.h>
#define sd(a) scanf("%d",&a)
#define mst(a,b) memset(a,b,sizeof a)
#define mp make_pair
typedef long long ll;
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int maxn = 2e5 + ;
//int inf = 0x3f3f3f3f;
const int mod = ;
ll dis[][];
vector<pii>g[];
bool vis[];
void dij(int s, int n) {
ll inf2 = 1e16;
for(int i = ; i <= n; ++i)
dis[s][i] = inf2, vis[i] = ;
dis[s][s] = ;
priority_queue<pair<ll, int> >q;
q.push(mp(, s));
for(; !q.empty();) {
int u = q.top().second;
q.pop();
if(vis[u])
continue;
vis[u] = ;
for(int j = , sz = g[u].size(); j < sz; ++j) {
int v = g[u][j].first;
int w = g[u][j].second;
if(dis[s][v] > dis[s][u] + w) {
dis[s][v] = dis[s][u] + w;
q.push(mp(-dis[s][v], v));
}
}
}
}
int s[], to[], t[];
ll dp[][][];
bool check(ll x, int n, int k) {
ll inf2 = 1e16;
for(int i = ; i <= k; ++i)
for(int j = ; j <= k; ++j)
dp[i][j][] = dp[i][j][] = inf2;
dp[][][] = ;
for(int i = ; i < k; ++i) {
for(int j = i; j <= k; ++j) {
for(int o = ; o < ; ++o) {
if(dp[i][j][o] == inf2)
continue;
if(!o) {
dp[i][j][] = min(dp[i][j][], dp[i][j][] + dis[to[i]][]);
if(j > i && i < k) {
ll time = dp[i][j][] + dis[to[i]][to[i + ]];
if(s[i + ] + x >= time)
dp[i + ][j][] = min(dp[i + ][j][], time);
}
} else {
if(j < k)
dp[i][j + ][] = min(dp[i][j + ][], max(dp[i][j][], (ll)t[j + ]) );
if(i < k && j >= i + ) {
ll time = dp[i][j][] + dis[][to[i + ]];
if(s[i + ] + x >= time)
dp[i + ][j][] = min(dp[i + ][j][], time);
}
}
}
}
}
return dp[k][k][] != inf2;
} int main() {
#ifdef local
freopen("in", "r", stdin);
#endif // local
int n, m;
sd(n), sd(m);
for(int i = ; i <= m; ++i) {
int u, v, w;
sd(u), sd(v), sd(w);
g[u].pb(mp(v, w));
g[v].pb(mp(u, w));
}
int k;
sd(k);
to[] = ;
for(int i = ; i <= k; ++i)
sd(s[i]), sd(to[i]), sd(t[i]);
for(int i = ; i <= n; ++i)
dij(i, n);
ll ans = 1e16;
ll l = , r = ans;
for(; l <= r;) {
ll mid = (l + r) >> ;
if(check(mid, n, k))
ans = mid, r = mid - ;
else
l = mid + ;
}
printf("%lld\n", ans);
return ;
}