CF1204C

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

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

相关阅读

相关 CF1214C

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

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

相关 CF1200C

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

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

相关 CF1197C

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

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

相关 CF1204C

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

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

相关 CF280C

CF280C > ZR补题计划题意： > 一棵有根树，每次选择一个未删除的节点，然后删除它和它的子树内的点，问期望删多少次可以把整个树删完解析： ...

刺骨的言语ヽ痛彻心扉/ 2024年04月20日 10:26/ 0 赞/ 60 阅读

相关 CF985C

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

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

相关【构造】CF1758 C

[Problem - 1758C - Codeforces][] 题意： ![ca2189d9b46747f4bd23ecfa1ef0db02.png][] 思路： !

古城微笑少年丶/ 2024年03月22日 23:17/ 0 赞/ 68 阅读

相关【MEX】CF1629 C

[Problem - C - Codeforces][] 题意： ![3b96010d5d4e4308a6e03f37a292c9af.png][] ![c7302633

た入场券/ 2024年03月17日 19:35/ 0 赞/ 71 阅读

相关 Codeforces 1204C

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

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

相关 cf 1179 C

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

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