难点：找出DP方程?

易错点：开long long

知识点：DP+任意一种最短路算法（Floyd都可以）

 

关于转移方程：

我们令DP[I]为第I天花费的最小“成本”

那么就有：

DP[i]=min{DP[j]+(i-j)*L+k}

0<j<i-1

我们可以这样理解，从第j天到第i天都采用当前（第i天）的最优方案

然后暴力更新即可？

一些易错点加在注释里面了

 

 1 #include<iostream>
 2 #include<cstring>
 3 #include<queue>
 4 #define int long long//主要因为懒
 5 using namespace std;
 6 inline int read(){
 7     char chr=getchar();    int f=1,ans=0;
 8     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
10     return ans*f;
11 }void write(int x){
12     if(x<0) putchar('-'),x=-x;
13     if(x>9) write(x/10);
14     putchar(x%10+'0');
15 }const int M = 1005; queue<int> q;
16 int t,n,m,k,e,dp[M],head[M],ver[M],nxt[M],val[M],tm[101][M],vis[M],tot,dis[M],bk[M];
17 inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];val[tot]=z;head[x]=tot;}
18 int GET(){memset(dis,127,sizeof(dis));memset(bk,0,sizeof(bk));//关于SPFA，它死了，但这里的小数据显然卡不掉啊 
19     while(!q.empty()) q.pop();q.push(1);dis[1]=0;bk[1]=1;//初始化 
20     while(!q.empty()){
21         int fx=q.front();q.pop();bk[fx]=0;
22         for(int i=head[fx];i;i=nxt[i]){
23             int v=ver[i];
24             if(vis[v]) continue;//在该时间访问非法节点 
25             if(dis[v]>dis[fx]+val[i])//松弛 
26                 dis[v]=dis[fx]+val[i],(!bk[v])?(q.push(v),bk[v]=1):1;
27         }
28     }return dis[m];
29 }signed main(){
30     n=read(),m=read(),k=read(),e=read();memset(dp,127,sizeof(dp));dp[0]=0;
31     while(e--){int x=read(),y=read(),z=read();add(x,y,z),add(y,x,z);}//读入并建图 
32     t=read();while(t--){int x=read(),y=read(),z=read();for(int i=y;i<=z;i++) tm[x][i]=1;}//读入并记录x号节点在y~z时间内是非法的
33 //-----------------读入和DP分割线（避免由于压行看不懂代码）------------------------------ 
34     for(int i=1;i<=n;i++,memset(vis,0,sizeof(vis)))
35         for(int j=i-1;j>=0;j--){ 
36             for(int k=1;k<=m;k++) if(tm[k][j+1]) vis[k]=1;//在这段时间内的非法节点
37             t=GET();if(t>=0x3f3f3f3f) break;
38             dp[i]=min(dp[i],dp[j]+(i-j)*t+k);//转移------ 
39         }return write(dp[n]-k),0;//由于第一次更新路径时也当做修改操作，加上了k，在最后减掉即可 
40 }