CF1204C

阳光穿透心脏的1/2处 2024-04-20 10:26 105阅读 0赞

##  ##

CF1204C-Anna, Svyatoslav and Maps

### 题意： ###

> [题目传送门][Link 1]  
> 不想说了，阅读题。

### 解法： ###

> 先用floyd跑出各顶点间的最短路。把p(1)加入答案，然后沿着题目给的路径序列遍历，如果答案中的最后一个顶点到当前遍历到的顶点的最短距离，小于原序列中两点的距离和，则答案加上p(i-1),并且继续遍历路径，遍历完之后在最后加上p(m)

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF = 0x3f3f3f3f; #define LL long long #define N 110 int e[N][N],ans[N*N*N]; int p[N*N*N],n,m,cnt; void floyd() { for(int k = 1 ; k <= n ; k++) { for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= n ; j++) { e[i][j] = min(e[i][j],e[i][k] + e[k][j]); } } } } int main(){ scanf("%d",&n); getchar(); for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= n ; j++) { char t = getchar(); e[i][j] = (t == '1') ? 1 : INF; if(i == j) e[i][j] = 0; } getchar(); } scanf("%d",&m); for(int i = 1 ; i <= m ; i++) scanf("%d",&p[i]); floyd(); ans[++cnt] = p[1]; int dis = 0; for(int i = 2 ; i <= m ; i++) { dis += e[p[i - 1]][p[i]]; if(dis > e[ans[cnt]][p[i]]){ ans[++cnt] = p[i - 1]; dis = e[ans[cnt]][p[i]]; } } ans[++cnt] = p[m]; printf("%d \n",cnt); for(int i = 1 ; i <= cnt ; i++) printf("%d ",ans[i]); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11391272.html

[Link 1]: https://codeforces.com/contest/1204/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，105人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1197C

CF1197C 题意： > 有一个递增的数列，把它分成k段，找到这样的分段方法，即每段最大值减最小值的和最小解法： > 分成k段，即要加k-1个隔...

太过爱你忘了你带给我的痛/ 2024年04月20日 10:28/ 0 赞/ 107 阅读

相关 CF1204C

CF1204C-Anna, Svyatoslav and Maps 题意： > [题目传送门][Link 1] > 不想说了，阅读题。解法： ...

阳光穿透心脏的1/2处/ 2024年04月20日 10:26/ 0 赞/ 106 阅读

相关 CF1204B

CF1204B-Mislove Has Lost an Array 题意： > 给你n，l，r 表示在区间1-n内至少有l个不相同的数至多有r个不相同的数，...

女爷i/ 2024年04月20日 10:26/ 0 赞/ 91 阅读

相关 CF1204A

CF1204A. BowWow and the Timetable 题意： > 给你一个2进制数，求这个2进制数在10进制中的 $ 4^i $ 的个数。 ...

痛定思痛。/ 2024年04月20日 10:26/ 0 赞/ 94 阅读

相关 CF985C

CF985C 题意： > 你要组成N个木桶，组成每个木桶需要K个木块，（第二行给你N\*K个木块），使得任意两个木桶之间的差值不超过L的情况，使得所有木桶可...

客官°小女子只卖身不卖艺/ 2024年04月20日 10:26/ 0 赞/ 96 阅读

相关【Floyd】CF1204 Anna, Svyatoslav and Maps

看错题意了一直看不懂题解浪费了好多时间... ![89d9fb3a0aa3436d85b758035ffeadea.png][]![8abf5d61438e40d099675

梦里梦外;/ 2024年03月22日 11:12/ 0 赞/ 65 阅读

相关序列递推——cf1204E（好题）

/ 显然用dp[i][j]来表示i个1，j个-1的结果 dp[i][j]由dp[i-1][j]和dp[i][j-1]转移而来即dp[i][j]对应的所有序列，都可以由

「爱情、让人受尽委屈。」/ 2023年10月11日 09:09/ 0 赞/ 78 阅读

相关 Codeforces 1204C

题意略。思路：我的想法是逐步地找出这个序列中的重要点，我要判断当前这个点能不能删去，就要看上一个重要点和当前这个点 i 在序列中的下一个点 i + 1之间的距离是否是最

忘是亡心i/ 2023年08月17日 16:37/ 0 赞/ 157 阅读

相关 CodeForces1204C

[CodeForces1204C][] 其实我觉得这是一道比较综合的题吧... 这个题可供挖掘的性质很多,比如最短路最长是\\(n\\)啊,答案序列中的两点之间的距离肯定

小咪咪/ 2023年06月02日 11:57/ 0 赞/ 27 阅读

相关 cf 1179 C

目录 A B C A 模拟出A不是最大值的情况，存起来。最多有n个。当A为最大值的时候，后面n-1个数开始循环。查询分两种情况讨论就行了

比眉伴天荒/ 2021年11月01日 10:20/ 0 赞/ 300 阅读