Description：

给一个带权无向图，对于每个点求是否有点对删掉这个点后最短路边长。

$1\leqslant n \leqslant200$

Solution：

先跑个 $floyed$ ，求出最短路及最短路条数，然后枚举每个点和点对，判断是否 $d[i][k]+d[k][j]=d[i][j]\&\&cnt[i][k]\times cnt[k][j]=cnt[i][j]$ ，如果是，就是重要的城市。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 210

int f[MAXN][MAXN];

typedef long long ll;

ll cnt[MAXN][MAXN];

bool tag[MAXN];

void check(int k)

{

    for(int i = 1;i <= n;++i)

    {

        for(int j = 1;j <= n;++j)

        {

            if(i == k || j == k || i == j)continue;

            if(f[i][k] + f[k][j] == f[i][j] && cnt[i][k] * cnt[k][j] == cnt[i][j])

            {

                tag[k] = true;

                return;

            }

        }

    }

    tag[k] = false;

    return;

}

int main()

{

    memset(f,0x3f,sizeof(f));

    scanf("%d%d",&n,&m);

    int a,b,x;

    for(int i = 1;i <= m;++i)

    {

        scanf("%d%d%d",&a,&b,&x);

        f[a][b] = f[b][a] = x;

        cnt[a][b] = cnt[b][a] = 1;

    }

    for(int k = 1;k <= n;++k)

    {

        for(int i = 1;i <= n;++i)

        {

            for(int j = 1;j <= n;++j)

            {

                if(f[i][k] + f[k][j] < f[i][j])

                {

                    f[i][j] = f[i][k] + f[k][j];

                    cnt[i][j] = 0;

                }

                if(f[i][k] + f[k][j] == f[i][j])

                {

                    cnt[i][j] += cnt[i][k] * cnt[k][j];

                }

            }

        }

    }

    bool found = false;

    for(int k = 1;k <= n;++k)

    {

        check(k);

        if(tag[k])

        {

            found = true;

            printf("%d ",k);

        }

    }

    if(!found)puts("No important cities.");

    puts("");

    return 0;

}