CF1204C

阳光穿透心脏的1/2处 2024-04-20 10:26 36阅读 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 条评论，36人围观）

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

相关阅读

相关 CF1214C

CF1214C 题意： > 给你一个括号序列，问你时候能仅移动相邻的两个元素，使括号序列合法。解法： > 可以先考虑普通括号序列怎么做 > 这...

亦凉/ 2024年04月20日 10:33/ 0 赞/ 35 阅读

相关 CF1200C

CF1200C 题意： > 问内圆和外圆分别分成n、m份，每份有标号，问是否可以从一个部分走到另一个部分，12点钟位置一定有个线。解法： > 如果...

旧城等待，/ 2024年04月20日 10:32/ 0 赞/ 48 阅读

相关 CF1204C

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

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

相关 CF1204B

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

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

相关 CF1204A

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

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

相关 CF985C

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

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

相关【Floyd】CF1204 Anna, Svyatoslav and Maps

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

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

相关序列递推——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 赞/ 15 阅读

相关 Codeforces 1204C

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

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

相关 cf 1179 C

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

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