[Jsoi2010]旅行
Time Limit: 30 Sec Memory Limit: 256 MB
Description
WJJ喜欢旅游，这次她打算去一个据说有很多漂亮瀑布的山谷玩。
WJJ事先得到了一张地图，上面标注了N(1< = N< = 50)个小动物的聚居地，也就是一个个的小村落。其中第1个村
庄是WJJ现在住的地方，第N个村庄是WJJ打算去的地方。这些村庄之间有M(1< = M< = 150)条双向道路连接着，第j
条双向道路恰好直接连接两个小村庄A，B，长度为C(1< = A，B < = N，Ai<>B, 1< = C< = 1000)。道路有的是隧
道，有的是栈桥，地图上那些看起来在村庄之外交叉的路实际上并不相交——也就是说，如果把这些小村落和双向
道路构成的道路网看作图论意义上的图，我们不保证它是平面图，也不保证它没有重边。不过，有一点还是可以保
证的：WJJ细心地验证过，从它居住的村落一定能走到她想去的那个山谷。
在WJJ所在的神奇世界中，每只小动物都可以借助仙人掌来施放魔法，其中之一是，交换世界中任意两条双向道路
的长度，同时保持其他道路的长度不变。按WJJ目前的魔法水平，她最多能使用K(1< = K< = 20)次这种道路长度交
换魔法。可惜的是，由于仙人掌刺比较多，WJJ并不打算带着它旅行，于是她会在家里完成想要的道路交换后再出
门。假设WJI的旅行途中不会有其他小动物进行道路交换来破坏她设计好的路线。为了尽快达到目的地，WJJ希望她
需要走的总距离越短越好。也就是说，使用最多K次魔法后，从村落1到村落N的最短距离是多少？
Input
第1行：3个用空格隔开的整数N，M，K
第2．．M+1行：每行是3个整数，用空格隔开，分别表示A，B C
Output
1个整数，表示使用最多K次魔法后，村落1和村落N之间的最短距离。
Sample Input
5 5 2
1 2 10
2 5 10
1 3 4
3 4 2
4 5 1
Sample Output
3
一个可行的方案是，对调第1条边和第4条边的长度，再对调第1条边和第5条边的长度。对调后的最短路径为1-->2-
->5，长度为3。显然没有比这更优的方案了。
这道题很优秀啊。。。我都不知道他是dp还是图论了。。。
最优解应该是将边排序以后前面挨着挨着用，后面的边本色出演。。。。
所以我们枚举一下我们挨着用一直用到哪里。。。
将所有边按照边权排序，如果用一个01串来表示每条边是否被使用，则交换边权后的01串是一个前面全是1，后面有0有1的串。那么我们枚举这个分界线L在哪里。对于每条路径，我们可以选择直接走过去，或者和前L条边中的一条交换权值。于是考虑用f[i][j][k]表示到第i个点，前L条边用了j条，交换了k次的最小代价。转移有三种情况：
??1、这条边是前L条边中的一条。f[arr[e]][j+1][k]=min(f[arr[e]][j+1][k]，f[i][j][k]+weight[j+1]) 这是因为边e和边j+1都是一定会被用到的，先用哪个无所谓，但是为了方便转移前L条边只能被从小到大使用。 ???2、这条边不在前L条边中。 ?????????1）f[arr[e]][j][k]=min(f[arr[e]][j][k]，f[i][j][k]+weight[e]) 直接使用边e ?????????2）f[arr[e]][j+1][k+1]=min(f[arr[e]][j+1][k+1]，f[i][j][k]+weight[j+1]) 将边e和前L条边中的一条交换。然后用最短路来维护这个东西。。。
#include<bits/stdc++.h>using namespace std;const int N = 105, M = 305;struct lpl{int p[2], len;}lin, edge[M];struct ld{int i, j, k;};int n, m, k, cnt, ans = 0x7fffffff, dis[N][M][N];bool vis[N][M][N];vector<int> point[N];queue<ld> q;inline bool cmp(lpl A, lpl B){return A.len < B.len;}inline void workk(int L){ ???ld now; int ii, jj, kk, qwe; memset(vis, false, sizeof(vis)); ???memset(dis, 0x3f, sizeof(dis)); dis[1][0][0] = 0; q.push((ld){1, 0, 0}); ???while(!q.empty()){ ???????now = q.front(); q.pop(); ii = now.i; jj = now.j; kk = now.k; vis[ii][jj][kk] = false; ???????for(int i = point[ii].size() - 1; i >= 0; --i){ ???????????qwe = point[ii][i]; int to = edge[qwe].p[ii == edge[qwe].p[0]]; ???????????if(qwe <= L){ ???????????????if(jj < L && dis[to][jj + 1][kk] > dis[ii][jj][kk] + edge[jj + 1].len){ ???????????????????dis[to][jj + 1][kk] = dis[ii][jj][kk] + edge[jj + 1].len; ???????????????????if(!vis[to][jj + 1][kk]){ ???????????????????????vis[to][jj + 1][kk] = true; q.push((ld){to, jj + 1, kk}); ???????????????????} ???????????????} ???????????} ???????????else{ ???????????????if(jj < L && kk < k && dis[to][jj + 1][kk + 1] > dis[ii][jj][kk] + edge[jj + 1].len){ ???????????????????dis[to][jj + 1][kk + 1] = dis[ii][jj][kk] + edge[jj + 1].len; ???????????????????if(!vis[to][jj + 1][kk + 1]){ ???????????????????????vis[to][jj + 1][kk + 1] = true; q.push((ld){to, jj + 1, kk + 1}); ???????????????????} ???????????????} ???????????????if(dis[to][jj][kk] > dis[ii][jj][kk] + edge[qwe].len){ ???????????????????dis[to][jj][kk] = dis[ii][jj][kk] + edge[qwe].len; ???????????????????if(!vis[to][jj][kk]){ ???????????????????????vis[to][jj][kk] = true; q.push((ld){to, jj, kk}); ???????????????????} ???????????????} ???????????} ???????} ???} ???for(int i = 0; i <= k; ++i) ans = min(ans, dis[n][L][i]);}int main(){ ???//freopen("data.in", "r", stdin); ???//freopen("lpl.out", "w", stdout); ???scanf("%d%d%d", &n, &m, &k); ???for(int i = 1; i <= m; ++i){ ???????scanf("%d%d%d", &lin.p[0], &lin.p[1], &lin.len); ????????cnt++; edge[cnt] = lin; ???} ???sort(edge + 1, edge + 1 + m, cmp); ???for(int i = 1; i <= m; ++i){ ???????point[edge[i].p[0]].push_back(i); point[edge[i].p[1]].push_back(i); ???} ???for(int i = 0; i <= m; ++i) workk(i); ???cout << ans; ???return 0;}bzoj4681 [Jsoi2010]旅行
原文地址：https://www.cnblogs.com/LLppdd/p/9242690.html