洛谷题解P1772【[ZJOI2006]物流运输】

题目描述

物流公司要把一批货物从码头\(A\)运到码头\(B\)。由于货物量比较大&＃xff0c;需要\(n\)天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线&＃xff0c;以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在&＃xff0c;有的时候某个码头会无法装卸货物。这时候就必须修改运输路线&＃xff0c;让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情&＃xff0c;会带来额外的成本。因此物流公司希望能够订一个\(n\)天的运输计划&＃xff0c;使得总成本尽可能地小。

输入输出格式

输入格式&＃xff1a;

第一行是四个整数\(n(l≤n≤100),m(l≤m≤20)\),\(k\)和\(e\)。\(n\)表示货物运输所需天数&＃xff0c;\(m\)表示码头总数&＃xff0c;\(k\)表示每次修改运输路线所需成本&＃xff0c;\(e\)表示航线条数。接下来e行每行是一条航线描述&＃xff0c;包括了三个整数&＃xff0c;依次表示航线连接的两个码头编号以及航线长度\((>0)\)。其中码头\(A\)编号为\(1\)&＃xff0c;码头\(B\)编号为\(m\)。单位长度的运输费用为\(1\)。航线是双向的。再接下来一行是一个整数d&＃xff0c;后面的d行每行是三个整数\(P(1&＃xff0c;\(a\)&＃xff0c;\(b(1≤a≤b≤n)\)。表示编号为P的码头从第\(a\)天到第\(b\)天无法装卸货物&＃xff08;含头尾&＃xff09;。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头\(A\)到码头\(B\)的运输路线。

输出格式&＃xff1a;

包括了一个整数表示最小的总成本。总成本&＃61;n天运输路线长度之和&＃43;K*改变运输路线的次数。

【题意】

平面上有\(m(m<&＃61;20)\)个点&＃xff0c;\(e\)条边&＃xff0c;需要你求\(n(n<&＃61;100)\)次从\(1\)号点到\(n\)号点的最短路&＃xff0c;如果你改变了最短路径&＃xff0c;那么需要另外花费\(k\)元。每一条路径可能会在某&＃xff08;些&＃xff09;个时间段内关闭&＃xff0c;问这n次最短路的总花费最小需要几元

【算法】

\(DP&＃43;\text{最短路}\)

【分析】

注&＃xff1a;部分摘自here

最优解问题明显就是一个dp&＃xff0c;而求两点之间的距离当然就是最短路了~

我们先考虑DP

• 设计状态

我们设dp[i]为前i天所需花费的最小费用

• 状态转移

f[i]&＃61;min(f[i],f[j-1]&＃43;(i-j&＃43;1) * L&＃43;K) &＃xff08;1<&＃61;j<&＃61;i)

什么意思呢? 就是第j天到第i天走同一条路&＃xff0c;并且这条路和第j-1天是不同的

• 最短路

那么第j天到第i天走的肯定是此时情况下的最短路了,所以L表示在当前情况下的\(1->m\)的最短路,可以用\(Spfa\)或\(Dijktra\)求解

• 考虑码头是否开启

那么现在就要考虑码头无法使用的情况了&＃xff0c;因为我们要保证第j天到第i天走的最短路是不能包括在这些天内不能经过的点的(哪怕是1天或是间断的几天都不行)

所以我们枚举j的时候可以从大到小枚举&＃xff0c;并且将第j天无法通过的点同j&＃43;1->i天无法通过的点塞入一个集合(数组)&＃xff0c;并且在求最短路时判断不经过集合(数组)中的点&＃xff0c;就可以求出从第j天到第i天经过未损坏的点从1到m的最短路了。

【代码】

#include
using namespace std;
int n,m,k,e;
int q;
vectorver[25];
vectoredge[25];
bool tf[105][25];
int dp[105];
int d[105];
bool flag[105];
inline int read()
{int tot&＃61;0;char c&＃61;getchar();while(c<&＃39;0&＃39;||c>&＃39;9&＃39;)c&＃61;getchar();while(c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;){tot&＃61;tot*10&＃43;c-&＃39;0&＃39;;c&＃61;getchar();}return tot;
}
inline void SPFA()
{memset(d,0x3f,sizeof(d));queueq;q.push(1);d[1]&＃61;0;while(q.size()){int now&＃61;q.front();q.pop();for(int i&＃61;0;i}
int main()
{n&＃61;read();m&＃61;read();k&＃61;read();e&＃61;read();for(int i&＃61;1;i<&＃61;e;i&＃43;&＃43;){int x&＃61;read(),y&＃61;read(),z&＃61;read();ver[x].push_back(y);edge[x].push_back(z);ver[y].push_back(x);edge[y].push_back(z);}q&＃61;read();for(int i&＃61;1;i<&＃61;q;i&＃43;&＃43;){int p&＃61;read(),a&＃61;read(),b&＃61;read();for(int j&＃61;a;j<&＃61;b;j&＃43;&＃43;)tf[j][p]&＃61;1;}memset(dp,0x3f,sizeof(dp));dp[0]&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)flag[j]&＃61;0;//for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;)if(tf[i][j])flag[j]&＃61;1;for(int j&＃61;i;j>&＃61;1;j--){for(int kk&＃61;1;kk<&＃61;m;kk&＃43;&＃43;)if(tf[j][kk])flag[kk]&＃61;1;/*cout<}