分析
方法一:这是我一开始想到的一种方法。我可以先预处理出所有的可行路径,因为m范围较小。一个dfs深搜过去,加一个状态压缩,就能得到路径上所有的节点以及路径的花费。剩下的就是dp的事情了。选出每一天的可行路径,然后枚举前一天走的路径。似乎是2^18*2^18,复杂度略大,可以优化一下。代码没来得及码。。。
方法二:这是小菜鸡发现自己的状压要爆炸,于是点开题解开始厚颜无耻
学习的结果。主要是要通过spfa预处理出一个co [ i ] [ j ] : 第 i 天到第 j 天走的最短路长度,然后就可以直接dp了
代码(方法二)
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=110,M=22; int n,m,k,e,tot; int h[M],nex[N<<2],ver[N<<2],pri[N<<2]; int sum[M],bl[2][M][N],dis[N]; ll f[N],co[N][N]; bool vis[M]; inline void add(int x,int y,int z) { nex[tot]=h[x]; ver[tot]=y; pri[tot]=z; h[x]=tot++; } inline bool check(int now,int l,int r) { for (int i=1;i<=sum[now];i++) if(!(bl[0][now][i]>r||bl[1][now][i]<l)) return 1; return 0; } inline int bfs(int x,int y) { memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); queue<int>q; dis[1]=0; q.push(1); while(!q.empty()) { int k=q.front();q.pop(); vis[k]=0; for (int i=h[k];~i;i=nex[i]) { int j=ver[i]; if(check(j,x,y)) continue; if(dis[j]>dis[k]+pri[i]) { dis[j]=dis[k]+pri[i]; if(!vis[j]) vis[j]=1,q.push(j); } } } return dis[m]; } int main() { memset(h,-1,sizeof(h)); scanf("%d%d%d%d",&n,&m,&k,&e); for (int i=1;i<=e;i++) { int x,y,z;scanf("%d%d%d",&x,&y,&z); add(x,y,z),add(y,x,z); } int d;scanf("%d",&d); while(d--) { int p,a,b;scanf("%d%d%d",&p,&a,&b); ++sum[p]; bl[0][p][sum[p]]=a; bl[1][p][sum[p]]=b; } for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) co[i][j]=bfs(i,j); for (int i=1;i<=n;i++) f[i]=i*co[1][i]; for (int i=2;i<=n;i++) for (int j=1;j<i;j++) f[i]=min(f[i],f[j]+(i-j)*co[j+1][i]+k); printf("%lld\n",f[n]); return 0; }