[luoguP1772] [ZJOI2006]物流运输（DP + spfa）

传送门

预处理cost[i][j]表示从第i天到第j天起点到终点的最短距离

f[i]表示前i天到从起点到终点的最短距离

f[0] = K

f[i] = min(f[i], f[j 1] + cost[j][i] + K)

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #define N 1001 #define min(x, y) ((x) < (y) ? (x) : (y)) int n, m, K, e, d, cnt; int f[N], cost[N][N]; bool b[N][N], flag[N], vis[N]; int head[N], to[N], next[N], val[N], dis[N]; //f[i]表示前i天从起点到终点的最小费用 //cost[i][j]表示从第i天到, b[i][j]表示第i个码头第j天是否不能用 std::queue <int> q; inline int read() inline void add(int x, int y, int z) inline int spfa() } } } return dis[m]; } int main() d = read(); for(i = 1; i <= d; i++) for(i = 1; i <= n; i++) for(j = i; j <= n; j++) memset(f, 127, sizeof(f)); f[0] = K; for(i = 1; i <= n; i++) for(j = 1; j <= i; j++) if(cost[j][i] <= 1e9) f[i] = min(f[i], f[j 1] + cost[j][i] * (i j + 1) + K); printf("%d\n", f[n]); return 0; }

　　

上一篇：[POJ2443]Set Operation（bitset）

下一篇：[luoguP1627] 中位数（模拟？）

---

DP spfa 最短路