Codeforces 1204C

忘是亡心i 2023-08-17 16:37 89阅读 0赞

题意略。

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

是否是最短距离，如果是，那么我们就可以化简掉当前这个点（当然，上一个重要点不能和下一个点 i + 1是同一个点）。

还有一种做法是判断三个连续的点，如果第一个点和第三个点之间没有直接的边相连，那么第二个点一定会通过，也就是说会被化简掉。

![1161042-20190821110213287-1940279397.png][]

代码如下：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 105;
    const int maxn1 = 1e6 + 5;
    const int F = 0x3f;
    const int INF = 0x3f3f3f3f;
    
    char graph[maxn][maxn];
    int path[maxn1],dp[maxn][maxn],n,m;
    
    int main(){
        scanf("%d",&n);
        for(int i = 1;i <= n;++i) scanf("%s",graph[i] + 1);
        for(int i = 1;i <= n;++i){
            for(int j = 1;j <= n;++j){
                dp[i][j] = graph[i][j] == '1' ? 1 : INF;
            }
        }
        scanf("%d",&m);
        for(int i = 0;i < m;++i) scanf("%d",&path[i]);
        for(int k = 1;k <= n;++k){
            for(int i = 1;i <= n;++i){
                for(int j = 1;j <= n;++j){
                    dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);
                }
            }
        }
        int temp,last = 0,cnt = 1;
        for(int i = 1;i < m - 1;++i){
            int len = (i + 1) - last;
            if(dp[path[last]][path[i + 1]] == len && path[last] != path[i + 1]) path[i] = -1;
            else{
                last = i;
                ++cnt;
            }
        }
        ++cnt;
        printf("%d\n",cnt);
        for(int i = 0;i < m;++i){
            if(path[i] == -1) continue;
            printf("%d%c",path[i],i == m - 1 ? '\n' : ' ');
        }
        return 0;
    }

转载于:https://www.cnblogs.com/tiberius/p/11387493.html

[1161042-20190821110213287-1940279397.png]: /images/20230810/69ebf0c7ae6c4cfb81f42172aa924df5.png