我用的是Dijkstra+DP（当然是参考大佬们的啦），Dijkstra用来进行预处理，处理出dis[start_time][end_time] --[start_time,end_time]时间段的1->m的最短路，其实很简单，我们首先要把在某个时间段不能装卸货物的码头给预处理出来，可以用前缀和来处理，具体看代码，所以当到达这样点时，我们直接continue。DP阶段，我们初始dp[0]=-k,为什么？因为 0 时间没有通过任何码头，并且我们到第一次运行的航线还要交换一次航线，所以是-k,因为要抵消交换一次航线的代价。转移方程 是：dp[i]=min(dp[i],dp[j]+dis[j+1][i]*(i-j)+k)。
还有就是 当dis[j+1][i]是INF时，不要进行转移（INF很大的情况，我的INF=1e18,习惯问题），因为爆long long了。
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;typedef long long ll;
typedef pair<ll,int>P;
const int maxn=100;
const int day=200;
const ll INF=1e18;struct Edge{int to;ll len;Edge(int to_=0,ll len_=0){to=to_;len=len_;}
};
vector<Edge>G[maxn];
ll distan[maxn];
ll dis[day][day];
ll dp[day];
int notok[maxn][day];
bool vis[maxn];
int n,m,k,e,d;void Dijkstra(int stime,int etime){for(int i=0;i<maxn;i++) distan[i]=INF,vis[i]=false;distan[1]=0;priority_queue<P,vector<P>,greater<P> >que;que.push(P(0,1));int u,v,len;while(!que.empty()){P p=que.top();que.pop();u=p.second;if(vis[u]) continue;vis[u]=true;len=G[u].size();for(int i=0;i<len;i++){Edge e=G[u][i];v=e.to;if(notok[v][etime]-notok[v][stime-1]>0) continue;if(!vis[v]&&distan[v]>distan[u]+e.len){distan[v]=distan[u]+e.len;que.push(P(distan[v],v));}}}dis[stime][etime]=distan[m];
}int main(){scanf("%d%d%d%d",&n,&m,&k,&e);for(int i=0;i<e;i++){int u,v;ll len;scanf("%d%d%lld",&u,&v,&len);G[u].push_back(Edge(v,len));G[v].push_back(Edge(u,len));} scanf("%d",&d);for(int i=0;i<d;i++){int t,stime,etime;scanf("%d%d%d",&t,&stime,&etime);for(int j=stime;j<=etime;j++) notok[t][j]=1;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){notok[i][j]+=notok[i][j-1];}}for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){Dijkstra(j,i);}}dp[0]=(ll)-k;for(int i=1;i<=n;i++){dp[i]=INF;for(int j=0;j<i;j++){if(dis[j+1][i]!=INF) dp[i]=min(dp[i],dp[j]+dis[j+1][i]*(ll)(i-j)+(ll)k);}}printf("%lld\n",dp[n]);
}