减舟'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;
}

写的时候RE了，然后调了下，发现要在SPFA里改成滚动数组，不然边数比较多会溢出。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct node {
	int t, v;   
};
const int M = 2000001;
int n, m, pn, a[1001][1001][2], D[2000001], f[2000001];
bool b[2000001];
vector <node> G[2000001];
     
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", &n, &m);
	pn = 2;
	for (int i = 1; i < n; i++)
    	for (int j = 1; j < m; j++)
        	for (int k = 0; k <= 1; k++)
            	a[i][j][k] = ++pn;
	for (int i = 1; i <= pn; i++) G[i].clear();
	
	for (int i = 1; i < n; i++) a[i][0][1] = 1;
	for (int i = 1; i < m; i++) a[n][i][1] = 1;
	for (int i = 1; i < n; i++) a[i][m][0] = 2;
	for (int i = 1; i < m; i++) a[0][i][0] = 2;
    
	int tmp;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < m; j++)
			scanf("%d", &tmp), add(a[i - 1][j][0], a[i][j][1], tmp);
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &tmp), add(a[i][j - 1][1], a[i][j][0], tmp);
	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++)
			scanf("%d", &tmp), add(a[i][j][0], a[i][j][1], tmp);
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	init();
	
	int head = 0, tail = 1;
	memset(b, 0, sizeof(b));
	memset(D, 0x3f, sizeof(D));
	D[1] = 0; b[1] = 1; f[1] = 1;
	while (head < tail) {
    	int tmp = f[++head]; b[tmp] = 0;
    	if (head == M) head = 0;
		for (int i = 0; i < G[tmp].size(); i++)
			if (D[G[tmp][i].t] > D[tmp] + G[tmp][i].v) {
				D[G[tmp][i].t] = D[tmp] + G[tmp][i].v;
				if (!b[G[tmp][i].t]) {
					b[G[tmp][i].t] = 1, f[++tail] = G[tmp][i].t;
					if (tail == M) tail = 0;
				}
			}
	}
	printf("%d\n", D[2]);
	return 0;
}