很神经的一道题。
令 \(val_{i,j}\) 表示从第 \(i\) 天到第 \(j\) 天每天都走一条道路，单次的最小花费。可以枚举 \(\{i,j\}\) 然后把在这个区间里的所有点设置成不可达，每一个 \(\{i,j\}\) 都可以用 floyd 算，时间复杂度 \(O(n^2m^3)\)。
令 \(f_i\) 表示第 \(i\) 天的最小花费，那么我们有 \(f_i=\min_{j=1}^{i-1}(f_j+val_{j+1,i}\times (j-i)+k)\)。
点击查看代码
#include<bits/stdc++.h>
#define int ll
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();
#define ll long long
#define i128 __int128
using namespace std;
inline int read() {
int xx= 0;int f= 1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f= -1;
c= getchar();
}
while(c>='0'&&c<='9') {
xx= (xx<<1)+(xx<<3)+(c^48);
c= getchar();
}
return xx*f;
}
#define maxn 200050
int G[22][22];
int val[110][110];
int n,m,k,e;
vector<int> g[110];
int dis[22][22];
bool vis[22];
ll dp[110];
void pre_dis(int l,int r) {
m0(vis);
For(i,1,m) For(j,1,m) dis[i][j]=G[i][j];
For(i,1,m) dis[i][i]=0;
For(i,l,r) {
for(auto u:g[i])
vis[u]=1;
}
For(i,1,m) {
if(vis[i]) {
For(j,1,m) dis[i][j]=1e9,dis[j][i]=1e9;
}
}
For(k,1,m) For(i,1,m) For(j,1,m) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
val[l][r]=dis[1][m];
}
signed main() {
in2(n,m); in2(k,e);
mem(G,0x3f);
For(i,1,e) {
int u,v,d;
in3(u,v,d);
G[u][v]=G[v][u]=min(G[u][v],d);
}
int _=read();
while(_--) {
int p,a,b;
in3(p,a,b);
For(i,a,b) g[i].push_back(p);
}
For(i,1,n) For(j,i,n)
pre_dis(i,j);
For(i,1,n) {
dp[i]=val[1][i]*i;
For(j,1,i-1)
dp[i]=min(dp[i],dp[j]+val[j+1][i]*(i-j)+k);
}
cout<<dp[n];
}