P1772 [ZJOI2006]物流运输(最短路+dp或dfs+状压)

$又是一个神仙题$

点我去写呀

$\color{Red}Ⅰ.最短路+线性dp$

$不管怎么写,多无法处理在什么时候选哪条路,什么时候换乘$

$所以只得考虑dp$

$又因为数据范围极小只有20个点,直接暴力预处理一个cost数组$

$cost[i][j]表示i天到j天利用能走的点,从1到m的最短路$

$那么dp就比较显然了,dp[i]为前i天的最小花费,枚举在j+1天换乘$

$dp[i]=min(dp[i],dp[j]+cost[j+1][i]*(j-i)+k)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=209;
int inf,n,m,k,e,cost[maxn][maxn];
struct p{int to,nxt,w;
}d[maxn*maxn]; int head[maxn*maxn],cnt=1;
int dis[maxn],dp[maxn],isok[maxn],vis[maxn],cl[maxn][maxn];
void add(int u,int v,int w){d[cnt]=(p){v,head[u],w}, head[u]=cnt++;
}
void spfa()
{queue<int>q;for(int i=0;i<=m;i++)	dis[i]=1e9;memset(vis,0,sizeof(vis) );q.push(1);dis[1]=0, vis[1]=1, inf=dis[0];while( !q.empty() ){int u=q.front(); q.pop();vis[u]=0;for(int i=head[u];i;i=d[i].nxt){int v=d[i].to;if( isok[v] )	continue;if( dis[v]>dis[u]+d[i].w ){dis[v]=dis[u]+d[i].w;if( !vis[v] )	q.push(v),vis[v]=1;}}}
}
signed main()
{cin >> n >> m >> k >> e;for(int i=1;i<=e;i++){int l,r,w;cin >> l >> r >> w;add(l,r,w); add(r,l,w);}cin >> e;//反正e变量没用了 for(int i=1;i<=e;i++){int num,q,w;cin >> num >> q >> w;for(int j=q;j<=w;j++)	cl[num][j]=1;//表示num航班第j天不能走 }for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)//预处理[i,j]天哪些航班不能走 {memset( isok,0,sizeof(isok) );for(int s=1;s<=m;s++)//枚举每一个航班 for(int q=i;q<=j;q++)//枚举每一天if( cl[s][q] )	isok[s]=1;//一旦有一天不能走,就标记为不能走 spfa();	cost[i][j]=dis[m]; }memset( dp,20,sizeof(dp) );for(int i=1;i<=n;i++)//前i天的最小花费{dp[i]=cost[1][i]*i;for(int j=0;j<=i-1;j++)//[j+1,i]换航班 dp[i]=min(dp[i],dp[j]+cost[j+1][i]*(i-j)+k );}cout << dp[n];
}

$\color{Red}Ⅱ.dfs+状压$

$这种方法就更巧妙了,难度也更高$

$由于最多只有20个点,起点终点已知,那么最多有1<<18种路径$

$用dfs把所有路径最短距离找出来,经过的点集压缩成二进制$

$然后把第i天不能走的点也压缩成二进制$

$第i天能使用状态j的路径条件是j\&(第i天路径的点集)==0$

$然后设dp[i][j]为第i天走路径j的最小花费$

$第一维可以滚动掉$

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=209;
int tmp[1<<20];
int vis[maxn],n,m,k,e,isok[maxn],ju[1<<20],dp[2][1<<20];
struct p{int to,nxt,w;
}d[maxn*maxn]; int head[maxn*maxn],cnt=1;
void add(int u,int v,int w){d[cnt]=(p){v,head[u],w}, head[u]=cnt++;
}
void dfs(int u,int zt,int dis)
{if( dis>=tmp[zt] )	return;tmp[zt]=dis;if( u==m ){zt^=(1<<(m-2));//m点不压缩 ju[zt]=min(ju[zt],dis);return;}for(int i=head[u];i;i=d[i].nxt){int v=d[i].to,sda=zt;if( vis[v] )	continue;vis[v]=1;dfs(v,zt|(1<<(v-2)),dis+d[i].w);vis[v]=0;}
}
void init()
{memset(ju,0x3f,sizeof(ju));memset(tmp,0x3f,sizeof(tmp));
}
signed main()
{cin >> n >> m >> k >> e;init();int l,r,w,num,q;for(int i=1;i<=e;i++){cin >> l >> r >> w;add(l,r,w); add(r,l,w);}cin >> e;//反正e变量没用了 for(int i=1;i<=e;i++){cin >> num >> q >> w;for(int j=q;j<=w;j++)	isok[j]|=(1<<(num-2));//表示num航班第j天不能走 }vis[1]=1;dfs(1,0,0);int last=0;for(int i=1;i<=n;i++){int temp=1e9,t=(i&1);for(int j=0;j<(1<<(m-1));j++){if( ju[j]==1e9 )	{ dp[t][j]=1e9; continue;}if( isok[i]&j )	{ dp[t][j]=1e9; continue;}dp[t][j]=min( dp[t^1][j]+ju[j],last+k+ju[j] );temp=min(temp,dp[t][j]);}last=temp;}cout<<last;
}