减舟's Blog

具体做法是先用SPFA暴力求出dis[i][j]（在i-j这段时间始终畅通的最短路），然后用动归做。状态转移式似乎比较简单。

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
struct node {
	int t, v;
};
vector <node> G[21];
const int INF = 1 << 30;
int n, m, k, e, d, D[101][101], f[101];
bool sce[21][101];
bool clo[21];
	
void add(int A, int B, int C) {
	node t1 = {B, C}, t2 = {A, C};
	G[A].push_back(t1), G[B].push_back(t2);
}

void init() {
	scanf("%d%d%d%d", &n, &m, &k, &e);
	for (int i = 1; i <= m; i++) G[i].clear();
	for (int i = 1; i <= e; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	memset(sce, 0, sizeof(sce));
	scanf("%d", &d);
	for (int i = 1; i <= d; i++) {
		int p, a, b; scanf("%d%d%d", &p, &a, &b);
		for (int j = a; j <= b; j++)
			sce[p][j] = 1;
	}
}

int SPFA() {
	int head = 0, tail = 1, f[1000], dis[1000];
	bool b[21];
	memset(b, 0, sizeof(b));
	for (int i = 1; i <= m; i++) dis[i] = INF;
	b[1] = 1, f[1] = 1, dis[1] = 0;
	while (head < tail) {
		int T = f[++head]; b[T] = 0;
		for (int i = 0; i < G[T].size(); i++)
			if (!clo[G[T][i].t])
			if (dis[T] + G[T][i].v < dis[G[T][i].t]) {
				dis[G[T][i].t] = dis[T] + G[T][i].v;
				if (!b[G[T][i].t]) {
					b[G[T][i].t] = 1; f[++tail] = G[T][i].t;
				}
			}
	}
	return dis[m];
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	init();
	
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++) {
			memset(clo, 0, sizeof(clo));
			for (int k = 1; k <= m; k++)
				for (int l = i; l <= j; l++)
					clo[k] = clo[k] || sce[k][l];
			D[i][j] = SPFA();
		}
	f[0] = -k;
	for (int i = 1; i <= n; i++) f[i] = INF;
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			if (D[j][i] != INF && f[j - 1] != INF)
				if (f[j - 1] + D[j][i] * (i - j + 1) + k < f[i])
					f[i] = f[j - 1] + D[j][i] * (i - j + 1) + k;
	printf("%d\n", f[n]);
	return 0;
}