传送门
dp好题。
每一天要变更路线一定还是走最短路。
所以l~r天不变更路线的最优方案就是把l~r天所有不能走的点都删掉再求最短路。显然是可以dp的。
设f[i]表示第i天的最优花销。那么我们枚举在哪里切换路线更优，则有状态转移方程：
f[i]=min(f[j]+spfa(j,i)∗(i−j)+k)(j=1...i−1)" role="presentation" style="position: relative;">f[i]=min(f[j]+spfa(j,i)∗(i−j)+k)(j=1...i−1)f[i]=min(f[j]+spfa(j,i)∗(i−j)+k)(j=1...i−1)
其中spfa时只有合法的点参与。
另外可以bitset优化一波。
代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int day,n,K,E,f[105],cnt=0,first[30],d[30];
struct edge{int v,w,next;}e[20000];
bool in[30];
bitset<21>del[105];
inline void add(int u,int v,int w){e[++cnt].v=v,e[cnt].next=first[u],e[cnt].w=w,first[u]=cnt;}
inline int spfa(int l,int r){
queue<int>q;
bitset<21>dell;
for(int i=l;i<=r;++i)dell|=del[i];
for(int i=1;i<=n;++i)in[i]=false,d[i]=inf;
q.push(1),d[1]=0,in[1]=true;
while(!q.empty()){
int x=q.front();
q.pop(),in[x]=false;
for(int i=first[x];i;i=e[i].next){
int v=e[i].v;
if(dell[v])continue;
if(d[v]>d[x]+e[i].w){
d[v]=d[x]+e[i].w;
if(!in[v])in[v]=true,q.push(v);
}
}
}
return d[n];
}
int main(){
day=read(),n=read(),K=read(),E=read();
for(int i=1;i<=E;++i){
int a=read(),b=read(),c=read();
add(a,b,c),add(b,a,c);
}
int d=read();
while(d--){
int tmp=read(),a=read(),b=read();
for(int i=a;i<=b;++i)del[i][tmp]=1;
}
f[1]=spfa(1,1);
for(int i=2;i<=day;++i){
int tmp=spfa(1,i);
if(tmp!=inf)f[i]=tmp*i;
else f[i]=inf;
for(int j=1;j<i;++j){
tmp=spfa(j+1,i);
if(tmp!=inf)f[i]=min(f[i],f[j]+K+(i-j)*tmp);
}
}
cout<<f[day];
return 0;
}