bzoj1003: [ZJOI2006]物流运输(最短路+DP)
程序员文章站
2022-03-20 22:23:48
题目: "1003: [ZJOI2006]物流运输" 解析: 最短路+DP 我们用$no[i][j]$来表示$i$在第$j$天不可以经过 用$cost[i][j]$表示第$i$天到第$j$天的花费 在最短路的时候判断一下在第$i$天到第$j$天中哪些码头不可以走,在做最短路时跳过 最后设f[i]表示 ......
题目:
解析:
最短路+dp
我们用\(no[i][j]\)来表示\(i\)在第\(j\)天不可以经过
用\(cost[i][j]\)表示第\(i\)天到第\(j\)天的花费
在最短路的时候判断一下在第\(i\)天到第\(j\)天中哪些码头不可以走,在做最短路时跳过
最后设f[i]表示到第i天时的最小花费
转移方程
\(f[i] = min(f[i], f[j]+k+cost[j+1][i]*(i-j))\)
代码:
#include <bits/stdc++.h> using namespace std; const int n = 1010; const int inf = 0x3f3f3f3f; int n, m, k, e, num, t; int head[n], dis[n]; long long f[n], cost[n][n]; bool vis[n], no[n][n], mark[n]; struct node { int v, nx, w; } e[n]; struct edge { int id, dis; bool operator <(const edge &oth) const { return dis > oth.dis; } }; inline void add(int u, int v, int w) { e[++num] = (node) {v, head[u], w}, head[u] = num; } priority_queue<edge>q; void dijkstra(int s, int from, int to) { memset(dis, inf, sizeof dis); memset(vis, 0, sizeof vis); memset(mark, 0, sizeof mark); for (int i = 1; i <= m; ++i) for (int j = from; j <= to; ++j) if (no[i][j]) mark[i] = 1; dis[s] = 0; q.push((edge) {s, 0}); while (!q.empty()) { int u = q.top().id; q.pop(); if (vis[u]) continue; vis[u] = 1; for (int i = head[u]; ~i; i = e[i].nx) { int v = e[i].v; if (mark[v]) continue; if (dis[v] > dis[u] + e[i].w) q.push((edge) {v, dis[v] = dis[u] + e[i].w}); } } } signed main() { memset(head, -1, sizeof head); cin >> n >> m >> k >> e; for (int i = 1, x, y, z; i <= e; ++i) { cin >> x >> y >> z; add(x, y, z), add(y, x, z); } cin >> t; for (int i = 1, x, y, z; i <= t; ++i) { cin >> x >> y >> z; for (int j = y; j <= z; ++j) no[x][j] = 1; } for (int i = 1; i <= n; ++i) for (int j = i; j <= n; ++j) { dijkstra(1, i, j); cost[i][j] = dis[m]; } for (int i = 1; i <= n; ++i) ; for (int i = 1; i <= n; ++i) { f[i] = cost[1][i] * i; for (int j = 1; j <= i; ++j) { f[i] = min(f[i], f[j] + k + cost[j + 1][i] * (i - j)); } } cout << f[n]; }
上一篇: linux中 pmap 命令详解
下一篇: 2019新版UI设计面试题汇总(附答案)