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
     
       #include
      
        #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; }