P1772

灾后重建 题解

luogu P1772物流运输~~~~~~↑

首先，求最短路选择什么方法。第一眼看到数据范围n<=20，这么小，我就想去用Floyd，然后就彻底把自己绕进去了。事实上也不是不能用Floyd实现（不确定能不能过），记录一下这个村庄维修的时间，然后在第一层for循环内判一下是否能通行就可以了。

然而还是用dijkstra吧...施工的话直接记录下来，后面跑dij的时候vis标记一下就解决了。

f[i]表示前i天的代价最小值，转移方程f[i]=min(f[i],f[j]+(i-j)*dis[j+1][i]+c);，表示前j天的代价+第j+1到第i天换一条新路的代价。题解都有讲，在此不多赘述。这里主要记录一下自己的思考。能力过蒻所以很多地方不能一下想到。

比如说我一开始没有想到开一个dis[i][j]表示第i到第j天都能通行的一条最短路。不过确实有往这方面感性理解。不能直接找全局最短路，因为中间可能不通；也不能每一次都去找最短路，这样总是会有额外的换路费用c，至此可想到用dp了。

还是感性理解一下，怎么样才能保证最优？就是路既比较短又不用经常换，这个“不用经常换”启发我枚举时间作为dp转移的中间点，至此可想到设计f[i]表示前i天的代价最小值了，且最短路要与时间有关。

设想一种情况，假设这是最后一次换路了，则前面需要保证最优的条件就只需要满足“路比较短”了，那我们就只需要找一条从现在开始到最后时间都能走的最短路就可以了，至此想到设计dis[i][j]表示第i天到第j天都能通行的最短路长度，整个解题思路清晰了。

那么dij()里需要传两个参表示初始与结束时间，利用这个我们就能把提前记录过的不能通行的点的vis打标记了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=107,M=207;
int D,n,c,m,u,v,w,k,tot,head[M],vis[27],d[57],cons[27][N];
ll f[N],dis[N][N];
priority_queue<pair<int,int> > q;
struct node{
	int to,nxt,w;
}e[2*M];
void add(int x,int y,int z){
	e[++tot].to=y;
	e[tot].w=z;
	e[tot].nxt=head[x];
	head[x]=tot;
}
void clr(){
	memset(vis,0,sizeof vis);
	memset(d,0x3f,sizeof d);
}
int dij(int st,int ed){
	clr();
	for(int i = 1;i<=n;i++)
		for(int j = st;j<=ed;j++)
			if(cons[i][j])vis[i]=1;
	d[1]=0;
	q.push({0,1});
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(vis[x])continue ;
		vis[x]=1;
		for(int i = head[x];i;i=e[i].nxt){
			int y=e[i].to,w=e[i].w;
			if(d[y]>d[x]+w){
				d[y]=d[x]+w;
				q.push({-d[y],y});
			}
		}
	}
	return d[n];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	memset(f,0x3f,sizeof f);
	cin>>D>>n>>c>>m;
	for(int i = 1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);add(v,u,w);
	}
	cin>>k;
	while(k--){
		cin>>u>>v>>w;
		for(int i = v;i<=w;i++)cons[u][i]=1;//construction
	}
	for(int i = 1;i<=D;i++)
		for(int j = i;j<=D;j++)
			dis[i][j]=dij(i,j);//i~j天的最短路
	f[0]=-c;
	for(int i = 1;i<=D;i++)
        for(int j = 0;j<i;j++)
            f[i]=min(f[i],f[j]+(i-j)*dis[j+1][i]+c);  
	cout<<f[D]<<'\n';
	return 0;
}

开不开long long都见**啊最好开一部分 调了半天一直是负数。。

因为我们不知道具体什么时候改路线，也不知道怎么改最好，所以考虑动态规划。

设计 $dp_i$ 表示第 $i$ 天结束时，最小花费。然后我们规定 $j\sim i$ 天路线都是一样的，然后只访问这几天都没施工的，求出 $1$ 到 $n$ 的最短路。使用 $dp_j+dist+c$ 更新 $dp_i$ 即可。

初值 $dp_0=-c$，因为第一次改路线不需要花钱。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=25;
int d,n,c,m;
vector<pair<int,int> >G[N];
bool zhale[105][25],ok[25];
int dp[105];
int dis[25];
bool vis[25];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
signed main() {
//	freopen("ex.in","r",stdin);
//	freopen(".out","w",stdout);
	memset(dp,0x3f,sizeof dp);
	R(d),R(n),R(c),R(m);
	while(m--) {
		int R(u),R(v),R(w);
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	int R(T);
	while(T--) {
		int R(id),R(l),R(r);
		for(int j=l; j<=r; ++j)zhale[j][id]=1;
	}
	dp[0]=-c;
	for(int r=1; r<=d; ++r) {
		for(int l=1; l<=r; ++l) {
			memset(dis,0x3f,sizeof dis);
			memset(vis,0,sizeof vis);
			memset(ok,1,sizeof ok);
			while(!q.empty())q.pop();
			for(int id=1; id<=n; ++id) {
				for(int i=l; i<=r; ++i) {
					if(zhale[i][id]) {
						ok[id]=0;
						break;
					}
				}
			}
			dis[1]=0;
			q.push({0,1});
			while(!q.empty()) {
				int u=q.top().second;
				q.pop();
				if(vis[u])continue;
				vis[u]=1;
				for(auto pii:G[u]) {
					int v=pii.first,w=pii.second;
					if(!ok[v])continue;
					if(dis[v]>dis[u]+w) {
						dis[v]=dis[u]+w;
						q.push({dis[v],v});
					}
				}
			}
			if(dis[n]<1e16) dp[r]=min(dp[r],dp[l-1]+dis[n]*(r-l+1)+c);
		}
	}
	cout<<dp[d]<<"\n";
	return 0;
}