ZJOI2006 物流运输

https://www.luogu.com.cn/problem/P1772

这是一个非常神奇的动态规划+最短路问题

 

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
ll map[200][200];
int n, m, k, e;
int vis[400];
int f[300];
int fin[300][300];
ll dp[300];
int cnt[300];
struct Node {
	int p;
	int len;
	Node(int a, int b) :p(a), len(b) {}
};
bool operator <(const Node a, const Node b) {
	return a.len > b.len;
}
vector<Node>G[400];

ll dis[300];
int dij() {
	for (int i = 0; i <= m; i++) {
		dis[i] = 1e14;
	//	vis[i] = 0;
	}
	priority_queue<Node>que;
	que.push(Node(1, 0));
	dis[1] = 0;
	while (que.size()) {
		Node ans = que.top();
		que.pop();
		if (vis[ans.p]) continue;
		if (cnt[ans.p]) continue;
		vis[ans.p] = 1;
		for (int i = 0; i < G[ans.p].size(); i++) {
			int p = G[ans.p][i].p;
			if (dis[p] > dis[ans.p] + G[ans.p][i].len) {
				dis[p] = dis[ans.p] + G[ans.p][i].len;
				que.push(Node(p, dis[p]));
			}
		}
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k >> e;
	int be, en,len;
	for (int i = 0; i < e; i++) {
		cin >> be >> en >> len;
		G[be].push_back(Node(en, len));
		G[en].push_back(Node(be, len));
	}
	dij();
	
	int d;
	cin >> d;
	while (d--) {
		int x;
		cin >> x >> be >> en;
		for (int i = be; i <= en; i++) {
			fin[x][i] = 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <=n ; j++) {
			memset(vis, 0, sizeof(vis));
			for (int a = i; a <= j; a++) {
				for (int b = 1; b <= m; b++) {
					if (fin[b][a]) vis[b] = 1;
				}
			}
			dij();
			map[i][j] = dis[m];
		}
	}
	
	for (int i = 1; i <= n; i++) dp[i] = 1e18;


	for (int i = 0; i<=n; i++) {
		dp[i] = 1LL * map[1][i] * i;
		for (int j = i - 1; j >= 0; j--) {
			dp[i] = min(dp[i], dp[j] + map[j + 1][i] * (i - j) + k);
		}
	}
	cout << dp[n] << endl;
	return 0;
}