题目
最短路+DP
最短路可以用floyd或者spfa来处理出1到n的所有时间区间的最短路。
(dis[i][j][k][l])表示i到j在(k,l)时间内每个时间点都能走的节点的(i,j)之间的最短路。
因此我们可以预处理出来最短路，然后开始DP，设置(dp[i])为1到i之间的所有时间的最短路之和。然后就可以区间DP了。
#include <bits/stdc++.h>
using namespace std;
int t, n, m, k, d, flag[23], dis[23][23][110][110], check_tim[110][110];//check[p][m]表示p点在m的时间是否是对的。
int dp[201];
inline void floyd()
{
for (int ts = 1; ts <= t; ts++)
for (int te = 1; te <= t; te++)//从ts(每段时间的开始
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j][ts][te] = dis[i][j][0][0];
memset(flag, 0, sizeof(flag));
flag[n] = 1;
for (int tim = ts; tim <= te; tim++)
for (int i = 1; i <= n; i++)
if (check_tim[i][tim])
flag[i] = 1;
for (int k = 1; k <= n; k++)
if (!flag[k])
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j][ts][te] = min(dis[i][j][ts][te], dis[i][k][ts][te] + dis[k][j][ts][te]);
}
for (int i = 1; i <= t; i++)
dp[i] = dis[1][n][1][i] * i;
}
inline void init()
{
scanf("%d%d%d%d", &t, &n, &k, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
dis[i][j][0][0] = 1000007;
if (j == i) dis[i][i][0][0] = 0;
}
for (int i = 1, a, b, c; i <= m; i++)
scanf("%d%d%d", &a, &b, &c), dis[a][b][0][0] = dis[b][a][0][0] = min(dis[a][b][0][0], c);
scanf("%d", &d);
for (int i = 1; i <= d; i++)
{
int p, l, r;
scanf("%d%d%d", &p, &l, &r);
for (int j = l; j <= r; j++)
check_tim[p][j] = 1;
}
floyd();
}
int main()
{
init();
for (int i = 1; i <= t; i++)
for (int j = 1; j <= i; j++)
dp[i] = min(dp[i], dp[j - 1] + dis[1][n][j][i] * (i - j + 1)+ k);//j时间之前的值+k+
printf("%d", dp[t]);
return 0;
}