看题目描述中，码头的个数小的可怜，竟然只有20，一开始想会不会又是网络流或者状压DP啥的。（好像状压DP真能做QAQ）
不过读完题之后，发现这应该是一道求最短路的题，而且还不只是最短路，既然又可以改道又要求最小花费，那么肯定还有DP.
最短路+DP的结合题。我们可以这么考虑，反正这题数据范围贼小，我们不如先预处理出来第i天到第j天全部能跑的一条最短路的长度是多少（如果不存在就是INF），之后呢，我们用dp[i]来表示到第i天的最小花费。那么就可以得知，dp[i] = min(dp[i],dp[j] + cost[j+1][i] + k);枚举从1到i-1的j 就可以了。
为什么可以这么做呢？我们考虑，如果有一条路，在第n天可以走，而在第n+1天不能走，那么此时我们就必须要改道。而改道我们直接在DP的时候考虑就好，那我们只要去求每种情况下不改道的话花费就可以。之后在DP枚举的时候，总会枚举到所有的改道和不改道的情况的。注意cost如果不是INF，要乘以其能走的天数。
这样可以保证考虑到所有情况。时间复杂度n^2*m^2,可以过。
看一下代码。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #include<set> #include<utility> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; typedef pair<int,int> pr; const int INF = 2e9; const int M = 2005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct node { int next,to,v; }e[M<<1]; set <pr> q; set <pr> :: iterator it; int ecnt,head[M],n,m,k,ei,d,p,a,b,cost[105][105],dp[105],dis[25],x,y,z; bool pd[30][105],bro[30]; void add(int x,int y,int z) { e[++ecnt].to = y; e[ecnt].v = z; e[ecnt].next = head[x]; head[x] = ecnt; } int dij(int s) { rep(i,1,m) dis[i] = INF; dis[s] = 0,q.insert(make_pair(dis[s],s)); while(!q.empty()) { pr now = *(q.begin()); q.erase(q.begin()); for(int i = head[now.second];i;i = e[i].next) { if(dis[e[i].to] > dis[now.second] + e[i].v && !bro[e[i].to]) { it = q.find(make_pair(dis[e[i].to],e[i].to)); if(it != q.end()) q.erase(it); dis[e[i].to] = dis[now.second] + e[i].v; q.insert(make_pair(dis[e[i].to],e[i].to)); } } } return dis[m]; } int main() { n = read(),m = read(),k = read(),ei = read(); rep(i,1,ei) x = read(),y = read(),z = read(),add(x,y,z),add(y,x,z); d = read(); rep(i,1,d) { p = read(),a = read(),b = read(); rep(j,a,b) pd[p][j] = 1; } rep(i,1,n) { rep(j,i,n) { memset(bro,0,sizeof(bro)); rep(f,1,m) rep(c,i,j) bro[f] |= pd[f][c]; cost[i][j] = dij(1); } } rep(i,1,n) rep(j,i,n) if(cost[i][j] < INF) cost[i][j] *= (j-i+1); rep(i,1,n) dp[i] = cost[1][i]; rep(i,2,n) rep(j,1,i-1) dp[i] = min(dp[i],dp[j] + cost[j+1][i] + k); printf("%d ",dp[n]); return 0; }