題目鏈接：

https://www.lydsy.com/JudgeOnline/problem.php?id=1003

題目大意：

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

思路：

先預(yù)處理出在時(shí)間a-b內(nèi)的最短路。

然后進(jìn)行dp

dp[i]表示前i天的最小花費(fèi)

狀態(tài)轉(zhuǎn)移方程：dp[i] = min(dp[i], dp[j] + cost[j + 1][j] * (i - j) + k);

dp[i]初始化為cost[1][i] * i;

1 #include<bits/stdc++.h> 2 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf 3 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函數(shù)，會(huì)超時(shí) 4 #define Min(a, b) ((a) < (b) ? (a) : (b)) 5 #define Mem(a) memset(a, 0, sizeof(a)) 6 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1)) 7 #define MID(l, r) ((l) + ((r) - (l)) / 2) 8 #define lson ((o)<<1) 9 #define rson ((o)<<1|1) 10 #define Accepted 0 11 #pragma comment(linker, "/STACK:102400000,102400000")//棧外掛 12 using namespace std; 13 inline int read() 14 { 15 int x=0,f=1;char ch=getchar(); 16 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 17 while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 18 return x*f; 19 } 20 21 typedef long long ll; 22 const int maxn = 100 + 10; 23 const int MOD = 1000000007;//const引用更快，宏定義也更快 24 const int INF = 1e9 + 7; 25 const double eps = 1e-6; 26 27 struct edge 28 { 29 int v; 30 ll w; 31 edge(){} 32 edge(int v, ll w):v(v), w(w){} 33 }; 34 vector<edge>e; 35 vector<int>Map[maxn]; 36 void addedge(int u, int v, ll w) 37 { 38 e.push_back(edge(v, w)); 39 Map[u].push_back(e.size() - 1); 40 } 41 struct Heapnode 42 { 43 ll d; 44 int u; 45 Heapnode(){} 46 Heapnode(ll d, int u):d(d), u(u){} 47 bool operator < (const Heapnode& a)const 48 { 49 return d > a.d; 50 } 51 }; 52 53 bool v[maxn];//標(biāo)記加入隊(duì)列 54 ll d[maxn];//最短路 55 bool judge[maxn][maxn];//judge[i][j]為真表示第i個(gè)碼頭在j時(shí)刻不可以工作 56 bool tmp[maxn];//tmp[i]表示碼頭i在a-b時(shí)間段內(nèi)是否可以工作 57 int n, m; 58 ll dijkstra(int a, int b, int s, int t)//在時(shí)間a-時(shí)間b內(nèi) 從s-t的最短路 59 { 60 for(int i = 1; i <= m; i++)//預(yù)處理 61 { 62 tmp[i] = 1; 63 for(int j = a; j <= b; j++) 64 { 65 if(judge[i][j]){tmp[i] = 0;break;} 66 } 67 } 68 priority_queue<Heapnode>q; 69 for(int i = 1; i <= m; i++)d[i] = INF; 70 d[s] = 0; 71 memset(v, 0, sizeof(v)); 72 q.push(Heapnode(0LL, s)); 73 while(!q.empty()) 74 { 75 Heapnode now = q.top(); 76 q.pop(); 77 int u = now.u; 78 if(v[u])continue; 79 v[u] = 1; 80 for(int i = 0; i < Map[u].size(); i++) 81 { 82 int v = e[Map[u][i]].v; 83 ll w = e[Map[u][i]].w; 84 if(!tmp[v])continue;//v不可以工作 85 if(d[v] > d[u] + w) 86 { 87 d[v] = d[u] + w; 88 q.push(Heapnode(d[v], v)); 89 } 90 } 91 } 92 return d[t]; 93 } 94 ll cost[maxn][maxn];//cost[a][b]表示從時(shí)間a-時(shí)間b內(nèi)的最短路 95 ll dp[maxn];//dp[i]表示前i天的最小花費(fèi) 96 int main() 97 { 98 int k, e; 99 scanf("%d%d%d%d", &n, &m, &k, &e); 100 for(int i = 1; i <= e; i++) 101 { 102 int u, v; 103 ll w; 104 scanf("%d%d%lld", &u, &v, &w); 105 addedge(u, v, w); 106 addedge(v, u, w); 107 } 108 scanf("%d", &e); 109 for(int i = 1; i <= e; i++) 110 { 111 int u, a, b; 112 scanf("%d%d%d", &u, &a, &b); 113 for(int j = a; j <= b; j++)judge[u][j] = 1; 114 } 115 for(int a = 1; a <= n; a++) 116 for(int b = 1; b <= n; b++) 117 cost[a][b] = dijkstra(a, b, 1, m); 118 for(int i = 1; i <= n; i++) 119 { 120 dp[i] = cost[1][i] * i; 121 for(int j = 1; j < i; j++) 122 { 123 dp[i] = min(dp[i], dp[j] + cost[j + 1][i] * (i - j) + k); 124 } 125 } 126 cout<<dp[n]<<endl; 127 return Accepted; 128 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/fzl194/p/9679751.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1003 物流运输 最短路+dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。