图论+DP的一道题，可以贪心地发明，要使路径最短，把路径按长度从小到大排序后，必定会把前\(fr\)条路径布置到走的路径上，每次交换也是将前\(fr\)条路径与\(fr\)后的路径交换，至于\(fr\)为几多我们可以枚举\(fr\)，然后DP求出\(ans\)

设\(f[i][j][k]\)暗示从1走到\(i\),在前\(fr\)条路径上已经走过了\(j\)条，已经交换了\(k\)条路径所颠末的最小长度，然后分三种情况转移一下就可以了，怎么转移看一下代码吧，其实是我不想写了，主要是挺多的，代码又臭又长

if(num<=fr) { if(jjj<fr&&dis[son][jjj+1][kkk]>dis[xxx][jjj][kkk]+e[jjj+1].w) { dis[son][jjj+1][kkk]=dis[xxx][jjj][kkk]+e[jjj+1].w; if(!vis[son][jjj+1][kkk]) vis[son][jjj+1][kkk]=1,txt.xx=son,txt.jj=jjj+1,txt.kk=kkk,q.push(txt); } } else { if(jjj<fr&&kkk<k&&dis[son][jjj+1][kkk+1]>dis[xxx][jjj][kkk]+e[jjj+1].w) { dis[son][jjj+1][kkk+1]=dis[xxx][jjj][kkk]+e[jjj+1].w; if(!vis[son][jjj+1][kkk+1]) vis[son][jjj+1][kkk+1]=1,txt.xx=son,txt.jj=jjj+1,txt.kk=kkk+1,q.push(txt); } if(dis[son][jjj][kkk]>dis[xxx][jjj][kkk]+e[num].w) { dis[son][jjj][kkk]=dis[xxx][jjj][kkk]+e[num].w; if(!vis[son][jjj][kkk]) vis[son][jjj][kkk]=1,txt.xx=son,txt.jj=jjj,txt.kk=kkk,q.push(txt); } } } }

注意我们为了便利，每次交换路径的时候我们不必然要看与哪个路径交换，横竖前\(fr\)条路径城市取到，，就直接从小往大加就行了

把全部的代码贴上来

#include<bits/stdc++.h> using namespace std; struct node { int x,y,w; } e[100003]; struct nod { int xx,jj,kk; } p,txt; queue<nod>q; int n,m,k,vis[53][153][23],dis[53][153][23],ans=1e9,xxx,jjj,kkk,num,son; vector<int>l[100003]; int cmp(node nx,node ny) { return nx.w<ny.w; } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1; i<=m; i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w); sort(e+1,e+m+1,cmp); for(int i=1; i<=m; i++) l[e[i].x].push_back(i),l[e[i].y].push_back(i); for(int fr=1; fr<=m; fr++) { memset(vis,0,sizeof(vis)); for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) for(int o=0; o<=k; o++) dis[i][j][o]=1e9; p.xx=1,p.jj=0,p.kk=0,q.push(p),vis[1][0][0]=1,dis[1][0][0]=0; while(!q.empty()) { p=q.front(),q.pop(),xxx=p.xx,jjj=p.jj,kkk=p.kk,vis[xxx][jjj][kkk]=0; for(int j=0; j<l[xxx].size(); j++) { num=l[xxx][j]; if(e[num].x==xxx) son=e[num].y; else son=e[num].x; if(num<=fr) { if(jjj<fr&&dis[son][jjj+1][kkk]>dis[xxx][jjj][kkk]+e[jjj+1].w) { dis[son][jjj+1][kkk]=dis[xxx][jjj][kkk]+e[jjj+1].w; if(!vis[son][jjj+1][kkk]) vis[son][jjj+1][kkk]=1,txt.xx=son,txt.jj=jjj+1,txt.kk=kkk,q.push(txt); } } else { if(jjj<fr&&kkk<k&&dis[son][jjj+1][kkk+1]>dis[xxx][jjj][kkk]+e[jjj+1].w) { dis[son][jjj+1][kkk+1]=dis[xxx][jjj][kkk]+e[jjj+1].w; if(!vis[son][jjj+1][kkk+1]) vis[son][jjj+1][kkk+1]=1,txt.xx=son,txt.jj=jjj+1,txt.kk=kkk+1,q.push(txt); } if(dis[son][jjj][kkk]>dis[xxx][jjj][kkk]+e[num].w) { dis[son][jjj][kkk]=dis[xxx][jjj][kkk]+e[num].w; if(!vis[son][jjj][kkk]) vis[son][jjj][kkk]=1,txt.xx=son,txt.jj=jjj,txt.kk=kkk,q.push(txt); } } } } for(int i=0; i<=k; i++) ans=min(ans,dis[n][fr][i]); } cout<<ans; return 0; }

[JSOI2010]旅行题解