题意：一条笔直街道上有标号为 1~n 的 n 个点，有 m 条带边权的单向边。要找一条经过 k 个点的路径和，限制：每次走过的边不能跨过已走过的点。 比如点 3 已经走过，则后面的边不能是 min(u,v) < 3 < max(u,v) 。
tags： 80 个点，一开始上暴搜 T 了，看了题解才知道是区间 dp。。
dp[cur][l][r][skip] 为当前走了skip步在 cur点，下一步可到达区间 [l,r] 状态，走完 k 步最少还要多少距离。
然后就是记忆化递归。
如果有边 cur -> to，且 to 在[l,r]之中，则 dp[cur][l][r][skip] = min(dp[cur][l][r][skip], dp[to][st][ed][skip+1] +边权 ) ； st, ed为走到 to后新的区间。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 85; int n, k, m, G[N][N]; int dp[N][N][N][N]; void Init() { mes(G, INF); mes(dp, -1); } int solve(int cur, int l, int r, int skip) { if(dp[cur][l][r][skip]!=-1) return dp[cur][l][r][skip]; // 这里dp不要定义为INF，因为下面不可能的情况会返回INF，这样不可能的情况就相当于没有记忆化 if(skip==k) return dp[cur][l][r][skip] = 0; int res = INF; rep(i,l,r) if(G[cur][i]!=INF) { int st=l, ed=r; if(i<cur) ed=cur-1; else st=cur+1; res = min(res, solve(i, st, ed, skip+1)+G[cur][i] ); } return dp[cur][l][r][skip] = res; } int main() { scanf("%d%d%d", &n, &k, &m); Init(); int u, v, w; rep(i,1,m) { scanf("%d%d%d", &u, &v, &w); G[u][v] = min(G[u][v], w); } int ans=INF; rep(i,1,n) ans = min(ans, solve(i, 1, n, 1) ); if(ans==INF) ans=-1; printf("%d ", ans); return 0; }