HYSBZ_1003
以前一直看不懂discuss的状态转移方程，后来某天早晨醒来的时候突然就发现我终于理解了……看来还是早晨的效率比较高。
可以用f[i]表示到第i天的时候最小费用，那么f[i]={f[j]+cost[j+1,i]+K}(0<=j<i)，其中cost[i,j]表示由第i天到第j天都可以走得通的最短路。
这样求完之后再减去一个多余的K即可。
#include<stdio.h>
#include<string.h>
#define MAXD 30
#define DAY 110
#define MAXQ 1010
#define INF 0x3f3f3f3f
int N, M, K, E, D, g[MAXD][MAXD], f[DAY], q[MAXQ], h[MAXD][DAY], A[MAXD][DAY], d[MAXD], inq[MAXD];
void init()
{
int i, j, k, x, y, z;
memset(g, 0, sizeof(g));
for(i = 0; i < E; i ++)
{
scanf("%d%d%d", &x, &y, &z);
if(g[x][y] == 0 || g[x][y] > z)
g[x][y] = g[y][x] = z;
}
memset(h, 0, sizeof(h));
scanf("%d", &D);
for(i = 0; i < D; i ++)
{
scanf("%d%d%d", &x, &y, &z);
for(j = y; j <= z; j ++)
h[x][j] = 1;
}
for(i = 1; i <= M; i ++)
{
A[i][0] = 0;
for(j = 1; j <= N; j ++)
A[i][j] = A[i][j - 1] + h[i][j];
}
}
int SPFA(int d1, int d2)
{
int i, j, k, front, rear;
front = rear = 0;
memset(d, 0x3f, sizeof(d));
memset(inq, 0, sizeof(inq));
q[rear ++] = 1;
d[1] = 0;
while(front != rear)
{
i = q[front ++];
inq[i] = 0;
for(j = 1; j <= M; j ++)
if(g[i][j] && A[j][d2] - A[j][d1] == 0 && d[i] + g[i][j] < d[j])
{
d[j] = d[i] + g[i][j];
if(!inq[j])
{
inq[j] = 1;
q[rear ++] = j;
}
}
}
return d[M];
}
void solve()
{
int i, j, k, t;
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for(i = 1; i <= N; i ++)
for(j = 0; j < i; j ++)
{
k = SPFA(j, i);
if(k != INF && ( t = f[j] + k * (i - j) + K) < f[i])
f[i] = t;
}
printf("%d\n", f[N] - K);
}
int main()
{
while(scanf("%d%d%d%d", &N, &M, &K, &E) == 4)
{
init();
solve();
}
return 0;
}