题解 P1841 【[JSOI2007]重要的城市】

木木！ · 2019-10-16 07:31:47 · 题解

提供一个比较不同的\Theta(n^3)思路。只需要跑一次最短路。

首先看数据范围为n\leq 200，可以发现\Theta(n^3)的Floyd可以碾过。然后不需要记录路径上的点，只需要记录最短路的个数就可以了。

在输出的时候，对于每一个点i，如果存在一对点j和k满足dist[j][i]+dist[i][k]==dist[j][k]并且num[j][i]*num[i][k]==num[j][k]，则说明j到k的所有最短路都要经过i。时间复杂度为\Theta(n^3)。

附AC代码：

#include <cstdio>
using namespace std;

inline void chkmin(int& a,int b)
{
    if(b<a)
    {
        a = b;
    }
}

int fi[205][205];
int ki[205][205];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=n; ++j)
        {
            fi[i][j] = 0x3f3f3f3f;
        }
        fi[i][i] = 0;
    }

    for(int i=1; i<=m; ++i)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        chkmin(fi[a][b],c);
        chkmin(fi[b][a],c);
        ki[a][b] = ki[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(fi[i][k]+fi[k][j] < fi[i][j])
                {
                    fi[i][j] = fi[i][k]+fi[k][j];
                    ki[i][j] = ki[i][k]*ki[k][j];
                }
                else if(fi[i][k]+fi[k][j] == fi[i][j])
                {
                    ki[i][j] += ki[i][k]*ki[k][j];
                }
            }
        }
    }

    for(int i=1; i<=n; ++i)
    {
        fi[i][i] = 0x3f3f3f3f;
    }

    bool flag = 0;
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=n; ++j)
        {
            for(int k=1; k<=n; ++k)
            {
                if(fi[j][k]==fi[j][i]+fi[i][k] && ki[j][k]==ki[j][i]*ki[i][k])
                {
                    printf("%d ",i);
                    flag = 1;
                    goto nxt;
                }
            }
        }

        nxt:;
    }

    if(!flag)
    {
        printf("No important cities.");
    }
}