传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1003
预处理出第i天到第j天走一条航线时的最短路。
#include#include #include const int maxn = 105, maxm = 25, maxe = 1005;int n, m, K, e, t1, t2, t3, dd;int head[maxm], to[maxe << 1], next[maxe << 1], w[maxe << 1], lb;int p[10005], a[10005], b[10005];char book[maxm], inq[maxm];int que[maxm], head_, tail, h, d[maxm], price[maxn][maxn];int f[maxn];inline void ist(int aa, int ss, int ww) { to[lb] = ss; next[lb] = head[aa]; head[aa] = lb; w[lb] = ww; ++lb;}inline void spfa(int start, int end) { memset(book, 0, sizeof book); for (int i = 0; i < dd; ++i) { if (a[i] <= end && b[i] >= start) { book[p[i]] = 1; } } if (book[1] || book[m]) { price[start][end] = 0x3c3c3c3c; return; } memset(que, 0, sizeof que); memset(d, 0x3c, sizeof d); memset(inq, 0, sizeof inq); head_ = tail = 0; que[tail++] = 1; inq[1] = true; d[1] = 0; while (head_ != tail) { h = que[head_++]; inq[h] = 0; if (head_ == m) { head_ = 0; } for (int j = head[h]; j != -1; j = next[j]) { if (!book[to[j]] && d[to[j]] > d[h] + w[j]) { d[to[j]] = d[h] + w[j]; if (!inq[to[j]]) { inq[to[j]] = 1; que[tail++] = to[j]; if (tail == m) { tail = 0; } } } } } price[start][end] = d[m];}int main(void) { //freopen("in.txt", "r", stdin); memset(next, -1, sizeof next); memset(head, -1, sizeof head); scanf("%d%d%d%d", &n, &m, &K, &e); while (e--) { scanf("%d%d%d", &t1, &t2, &t3); ist(t1, t2, t3); ist(t2, t1, t3); } scanf("%d", &dd); for (int i = 0; i < dd; ++i) { scanf("%d%d%d", p + i, a + i, b + i); } for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { spfa(i, j); } } f[0] = -K; for (int i = 1; i <= n; ++i) { f[i] = 2147483647; for (int j = 0; j < i; ++j) { if (price[j + 1][i] < 0x3c3c3c3c) { f[i] = std::min(f[i], f[j] + price[j + 1][i] * (i - j)); } } f[i] += K; } printf("%d\n", f[n]); return 0;}