CF1204C

CF1204C-Anna, Svyatoslav and Maps

题意：

题目传送门

不想说了，阅读题。

解法：

先用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;

}

巴特西

CF1204C

CF1204C-Anna, Svyatoslav and Maps

题意：

解法：

CODE:

最新文章

热门文章