題干：

題目描述

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

輸入輸出格式

輸入格式：

?

第一行是四個整數n(l≤n≤100)、m(l≤m≤20)、K和e。n表示貨物運輸所需天數，m表示碼頭總數，K表示每次修改運輸路線所需成本，e表示航線條數。接下來e行每行是一條航線描述，包括了三個整數，依次表示航線連接的兩個碼頭編號以及航線長度(>0)。其中碼頭A編號為1，碼頭B編號為m。單位長度的運輸費用為1。航線是雙向的。再接下來一行是一個整數d，后面的d行每行是三個整數P(1<P<m)，a，b(1≤a≤b≤n)。表示編號為P的碼頭從第a天到第b天無法裝卸貨物（含頭尾）。同一個碼頭有可能在多個時間段內不可用。但任何時間都存在至少一條從碼頭A到碼頭B的運輸路線。

?

輸出格式：

?

包括了一個整數表示最小的總成本?？偝杀?#61;n天運輸路線長度之和+K*改變運輸路線的次數。

?

輸入輸出樣例

輸入樣例#1：?復制

5 5 10 81 2 11 3 31 4 22 3 22 4 43 4 13 5 24 5 242 2 33 1 13 3 34 4 5

輸出樣例#1：?復制

32

說明

【樣例輸入說明】

上圖依次表示第1至第5天的情況，陰影表示不可用的碼頭。

【樣例輸出說明】

前三天走1-4-5，后兩天走1-3-5，這樣總成本為(2+2)*3+(3+2)*2+10=32。

_NOI導刊2010提高（01）

解題報告：

? ? 這題第一眼看的時候是沒思路的。。。聽學長講完woc好簡單。想到狀壓了但是不知道怎么用。

? 這題做法很多，其中一種就是先算出2^18中每一種狀態下，1到m的最短路是多少復雜度mlogm * 2^18，空間復雜度d[2^18]，應該不會爆。

? ?然后這題注意到不光點數很少，天數也很少，所以你可以預處理任意兩天之間，如果不更換線路的話，路徑最小值。也就是假設你要算i~j天的，所以首先要枚舉每一天然后處理出一個可行狀態來，然后直接與運算就可以得到可行狀態了，然后再你預處理的d數組中取數就可以了，這就是當前最優值。然后xjb做就可以了。

? 這題還有另一種十分好想并且不會卡空間的做法。詳情見代碼。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int INF = 0x3f3f3f3f; const int MAX = 2e5 + 5; struct Edge {int to,ne;ll w; } ee[MAX]; int n,m,k,e,D; ll dis[22],d[222][222]; int ban[22][222]; struct Point {int pos;ll c;Point(int pos,ll c):pos(pos),c(c){}bool operator < (const Point & b) const{return c > b.c;} }; int head[22],tot,vis[22]; void add(int u,int v,ll w) {ee[++tot].to = v;ee[tot].w = w;ee[tot].ne = head[u];head[u] = tot; } ll Dijkstra() {for(int i = 1; i<=m; i++) dis[i] = INF;priority_queue<Point> pq;pq.push(Point(1,0)); dis[1] = 0;while(pq.size()) {Point cur = pq.top();pq.pop();if(vis[cur.pos]) continue;vis[cur.pos] = 1;for(int i = head[cur.pos]; ~i; i = ee[i].ne) {int v = ee[i].to;if(vis[v]) continue;if(dis[v] > dis[cur.pos] + ee[i].w) {dis[v] = dis[cur.pos] + ee[i].w;pq.push(Point(v,dis[v]));}}}return dis[m]; } ll dp[222]; int main() {cin>>n>>m>>k>>e;for(int i = 1; i<=m; i++) head[i] = -1;for(int a,b,c,i = 1; i<=e; i++) {scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}cin>>D;for(int a,b,c,i = 1; i<=D; i++) {scanf("%d%d%d",&a,&b,&c);for(int j = b; j<=c; j++) ban[a][j] = 1;}for(int i = 1; i<=n; i++) {//枚舉每一區間段的起點 for(int j = i; j<=n; j++) {//枚舉終點 for(int tar = 1; tar<=m; tar++) {vis[tar]=0;for(int k = i; k<=j; k++) vis[tar] |= ban[tar][k];}d[i][j] = Dijkstra();//預處理出第i到第j天的最短路 } }memset(dp,INF,sizeof dp);dp[1] = d[1][1];for(int i = 2; i<=n; i++) {dp[i] = d[1][i]*i;for(int j = 2; j<=i; j++) {if(d[j][i]==INF) continue;dp[i] = min(dp[i],dp[j-1] + d[j][i]*(i-j+1) + k);}}printf("%lld\n",dp[n]);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【洛谷 - P1772 】[ZJOI2006]物流运输（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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