Luogu P1772 [ZJOI2006]物流运输

题目链接：​​传送门​​

很麻烦也很难想的一道题
数据很小大胆yy
详细解释在代码里

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <deque>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
  int next, to, w;
}e[A];
int head[A], num;
void add(int fr, int to, int w) {
  e[++num].next = head[fr];
  e[num].to = to;
  e[num].w = w;
  head[fr] = num;
}
int n, m, k, ee, q, a, b, c; ll f[B]/*第1天~第i天最小花费*/, w[B][B]/*从第i天到第j天最短路*/;
int clo[B][B]/*港口关闭情况*/, dis[B], vis[B], iso[B]/*一段时间内某港口能不能走*/;
int spfa(int s, int t) {
  memset(vis, 0, sizeof vis);
  memset(iso, 0, sizeof iso);
  memset(dis, 0x3f, sizeof dis);
  deque<int> q; dis[1] = 0; q.push_back(1);
  for (int i = 1; i <= m; i++)
    for (int j = s; j <= t; j++) //有一天关闭就不能走了
      if (clo[i][j]) iso[i] = 1; //因为求的是这几天共同的最小花费
  while (!q.empty()) {
    int fr = q.front(); q.pop_front(); vis[fr] = 0;
    for (int i = head[fr]; i; i = e[i].next) {
      int ca = e[i].to;
      if (iso[ca]) continue; //关了走不了啦
      if (dis[ca] > dis[fr] + e[i].w) {
        dis[ca] = dis[fr] + e[i].w;
        if (!vis[ca]) {
          vis[ca] = 1;
          if (q.empty() or dis[ca] > dis[q.front()]) q.push_back(ca);
          else q.push_front(ca);
        }
      }
    }
  }
  return dis[m];
}

int main(int argc, char const *argv[]) {
  scanf("%d%d%d%d", &n, &m, &k, &ee);
  for (int i = 1; i <= ee; i++) {
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c); add(b, a, c);
  }
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d%d", &a, &b, &c);
    for (int j = b; j <= c; j++) clo[a][j] = 1; //a港口在第j天关闭
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      w[i][j] = spfa(i, j);
  for (ll i = 1; i <= n; i++) {
    f[i] = w[1][i] * i; //没更换航线从1走过来走了i天花这些钱
    for (ll j = 1; j <= i; j++) //从第j天换航线,分为1~j和j~i,j~i的花费走了i-j天
      f[i] = min(f[i], f[j] + w[j + 1][i] * (i - j) + k);
  }
  cout << f[n] << endl;
}