描述

物流公司要把一批貨物從碼頭A運到碼頭B。由于貨物量比較大，需要n天才能運完。貨物運輸過程中一般要轉停好幾個碼頭。物流公司通常會設計一條固定的運輸路線，以便對整個運輸過程實施嚴格的管理和跟蹤。由于各種因素的存在，有的時候某個碼頭會無法裝卸貨物。這時候就必須修改運輸路線，讓貨物能夠按時到達目的地。但是修改路線是一件十分麻煩的事情，會帶來額外的成本。因此物流公司希望能夠訂一個n天的運輸計劃，使得總成本盡可能地小。

分析

• dp
• f[i] : 前i天最小成本
• f[i] = f[j] + k + cost[i+1][j] // cost[a][b] 表示第 a 天到第 b 天用同一條線路的成本.
• 用 spfa 預處理出 cost, 暴力的做法即可.

代碼

#include #include #include #include #include using namespace std; const int maxn = 20 + 5; const int maxm = 100 + 10; const int INF = 0x3f3f3f3f; struct Edge { int from, to, dist; }; struct SPFA { int n, m, s, t; int d[maxn]; bool ban[maxn], inq[maxn]; vectoredges; vectorG[maxn]; void init(int n, int s, int t) { this->n = n; this->s = s; this->t = t; } void AddEdge(int from, int to, int dist) { edges.push_back((Edge){from, to, dist}); edges.push_back((Edge){to, from, dist}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } int spfa(int x, int y) { queueQ; memset(d, 0x3f, sizeof(d)); Q.push(s); inq[s] = 1; d[s] = 0; while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(!ban[e.to] && d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; if(!inq[e.to]) Q.push(e.to), inq[e.to] = 1; } } } return d[t]; } }g; bool ban[maxn][maxm]; int dis[maxm][maxm], f[maxm]; int main() { int n, m, k, e, d; scanf("%d %d %d %d", &m, &n, &k, &e); g.init(n, 1, n); for(int i = 0; i < e; i++) { int from, to, dist; scanf("%d %d %d", &from, &to, &dist); g.AddEdge(from, to, dist); } scanf("%d", &d); for(int i = 0; i < d; i++) { int a, x, y; scanf("%d %d %d", &a, &x, &y); for(int j = x; j <= y; j++) ban[a][j] = 1; } for(int x = 1; x <= m; x++) for(int y = x; y <= m; y++) { memset(g.ban, 0, sizeof(g.ban)); for(int i = 1; i <= n; i++) for(int j = x; j <= y; j++) if(ban[i][j]) { g.ban[i] = 1; break; } dis[x][y] = g.spfa(x, y); } memset(f, 0x3f, sizeof(f)); f[0] = 0; for(int i = 1; i <= m; i++) for(int j = 0; j < i; j++) if(dis[j+1][i] != INF) f[i] = min(f[i], f[j] + k + dis[j+1][i]*(i-j)); printf("%d\n", f[m]-k); return 0; }

總結

以上是生活随笔為你收集整理的BZOJ-1003-物流运输trans-ZJOI2006-SPFA+DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。