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

· · 题解

怎么全都是Floyd...提供一个不一样的思路（可能蒟蒻脑回路清奇，第一思路就这个...）

一个城市x重要，当且仅当去掉它之后可以让s->t的最短路变化（s != t != x)。因为本题的n很小，我们可以枚举n作为s。

当确定s之后，以s为起点跑一次最短路，然后把所有在最短路上的边加入一个新图中。具体做法是：对于一条边，如果它起点处的最短路加上边权等于终点处的最短路，那么就把它加入新图中。

这个新图有一个很好的性质：它是一个DAG。原因很简单，最短路上没环= =。注意到这个最短路DAG记录了s为起点到所有点的最短路。

枚举1~n的每个点。如果存在边x->y，并且y的入度为1，那么删掉x之后y的入度会变成0，显然无法从s到达，即删掉x之后破坏了一些点的最短路。x就是一个关键点。

时间复杂度：枚举O(n)次，计算最短路O(mlogn)，求点xO(m)。所以总复杂度是O(nmlogn)。

#include <bits/stdc++.h>
using namespace std;

inline int rd() {
    int a = 1, b = 0; char c = getchar();
    while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
    while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
    return a ? b : -b;
}

const int N = 500, M = N * N;
struct Graph {
    int from, to, nxt, c;
} g[M * 2];
int head[N], tot;

void addedge(int x, int y, int c) {
    g[++tot].to = y, g[tot].from = x, g[tot].c = c,
    g[tot].nxt = head[x], head[x] = tot;
}

int n, m;

priority_queue<pair<int, int> > que;
int dis[N], in[N];
bool vis[N], important[N], mark[M];

void solve(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    que.push(make_pair(0, s));
    while (!que.empty()) {
        int x = que.top().second;
        que.pop();
        if (!vis[x]) {
            vis[x] = true;
            for (int i = head[x]; i; i = g[i].nxt) {
                int y = g[i].to;
                if (dis[y] > dis[x] + g[i].c) {
                    dis[y] = dis[x] + g[i].c;
                    que.push(make_pair(-dis[y], y));
                }
            }
        }
    }

    memset(mark, 0, sizeof(mark));
    memset(in, 0, sizeof(in));
    for (int i = 1; i <= tot; ++i) {
        if (dis[g[i].from] + g[i].c == dis[g[i].to]) {
            mark[i] = true;
            ++in[g[i].to];
        }
    }

    for (int i = 1; i <= tot; ++i)
        if (mark[i] && in[g[i].to] == 1 && g[i].from != s)
            important[g[i].from] = true;
}

int main() {
    n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
        int x = rd(), y = rd(), c = rd();
        addedge(x, y, c), addedge(y, x, c);
    }
    for (int i = 1; i <= n; ++i)
        solve(i);
    bool ok = false;
    for (int i = 1; i <= n; ++i)
        if (important[i]) {
            cout << i << " ";
            ok = true;
        }
    if (!ok) cout << "No important cities.";
    cout << endl;
    return 0;
}