[题解] [JSOI2010] 旅行

2021-04-20 13:27

阅读：566

标签：type problem while pre getc cst node getch empty

题面

题解

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

Code

#include 
#include 
#include 
#include 
#include 
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  p.d; 
        }
};
bool vis[N][M][25]; 
priority_queue q; 

template 
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c  '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c  (), m = read  (), K = read  ();
    ans = 0x3f3f3f3f; 
    for(int i = 1; i  (), V[i] = read  (), W[i] = read  (), c[i] = pir(W[i], i);
    sort(c + 1, c + m + 1);
    for(int i = 1; i

[题解] [JSOI2010] 旅行

标签：type problem while pre getc cst node getch empty

原文地址：https://www.cnblogs.com/ztlztl/p/12258427.html

上一篇：深入HTTP

下一篇：css省略号

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[题解] [JSOI2010] 旅行
文章链接：http://soscw.com/index.php/essay/77151.html

亲，登录后才可以留言！

[题解] [JSOI2010] 旅行

题面

题解

Code

评论

热门文章

推荐文章

最新文章

置顶文章