标签：

题面 题解

发明数据范畴很小， 考虑从这上面入手
不难发明， 如果我们把所有边的长度排序， 将每条边选与不选看作一个 01 串
假设最优路径长度为 L , 一定存在一个 \(K\) , 满足前 \(1 \to K\) 都是 1 ， 其他的随便
考虑枚举这个 \(K\)
设 \(f[i][j][k]\) 满足到 \(i\) 点，， 前 \(K\) 其中选了 \(j\) 条， 已经交换了 \(k\) 条
转移的话就是看这条边是不是可以换， 换不换就行
这里的转移方程和网上大部分的不太一样， 我把前 \(K\) 条的孝敬提前加上去了
发明可以最短路转移， 跑就对了

Code #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <queue> const int N = 55; const int M = 155; using namespace std; int head[N], cnt, n, m, K, sum[M], f[N][M][25], ans, U[M], V[M], W[M]; struct edge { int to, nxt, cost, id; } e[M << 1]; struct pir { int a, b; pir(int _a = 0, int _b = 0) { a = _a, b = _b; } bool operator < (const pir &p) const { return a < p.a; } } c[M << 1]; struct node { int a, b, c, d; node(int _a = 0, int _b = 0, int _c = 0, int _d = 0) { a = _a, b = _b, c = _c, d = _d; } bool operator < (const node &p) const { return d > p.d; } }; bool vis[N][M][25]; priority_queue<node> q; template < typename T > inline T read() { T x = 0, w = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * w; } inline void adde(int u, int v, int w, int id) { e[++cnt] = (edge) { v, head[u], w, id }, head[u] = cnt; } void dijkstra(int lim) { for(int i = 1; i <= n; i++) for(int j = 0; j <= lim; j++) for(int k = 0; k <= K; k++) f[i][j][k] = 0x3f3f3f3f, vis[i][j][k] = 0; f[1][0][0] = sum[lim]; q.push(node(1, 0, 0, f[1][0][0])); int u, j, k, w; while(!q.empty()) { node tmp = q.top(); q.pop(); u = tmp.a, j = tmp.b, k = tmp.c, w = tmp.d; if(vis[u][j][k]) continue; vis[u][j][k] = 1; for(int v, i = head[u]; i; i = e[i].nxt) { v = e[i].to; if(e[i].id <= lim) { if(j + 1 <= lim && w < f[v][j + 1][k]) { f[v][j + 1][k] = w; q.push(node(v, j + 1, k, f[v][j + 1][k])); } } else { if(w + e[i].cost < f[v][j][k]) f[v][j][k] = w + e[i].cost, q.push(node(v, j, k, f[v][j][k])); if(j < lim && k < K && w < f[v][j + 1][k + 1]) f[v][j + 1][k + 1] = w, q.push(node(v, j + 1, k + 1, f[v][j + 1][k + 1])); } } } for(int i = 0; i <= K; i++) ans = min(ans, f[n][lim][i]); } int main() { n = read <int> (), m = read <int> (), K = read <int> (); ans = 0x3f3f3f3f; for(int i = 1; i <= m; i++) U[i] = read <int> (), V[i] = read <int> (), W[i] = read <int> (), c[i] = pir(W[i], i); sort(c + 1, c + m + 1); for(int i = 1; i <= m; i++) adde(U[c[i].b], V[c[i].b], W[c[i].b], i), adde(V[c[i].b], U[c[i].b], W[c[i].b], i); for(int i = 1; i <= m; i++) sum[i] = sum[i - 1] + c[i].a; for(int i = 1; i <= m; i++) dijkstra(i); printf("%d\n", ans); return 0; }

[题解] [JSOI2010] 旅行