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

题面

题解

最短路图模板题。

介绍一下最短路图：

• 先对原图跑一边单源最短路,求出源点到每个点\(i\)的最短路\(dis[i]\).
• 接下来构建新图：对于一条边\((x,y,v)\),若\(dis[x]+v=dis[y]\)则在新图中加入这条边.
• 这样就构成了一个新图,满足\(DAG\)的性质

对于此题：

先建立最短路图，
考虑最短路图上的一条边\((x,y)\),若\(y\)的入度为\(1\),则\(x\)为重要的.

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar();}
    return f * x;
}

int tot, n, cnt, dis[1000003], m, qi[1000003], head[1000003], in[3000003], nxt[3000003], ver[1000003], edge[1000003], ans[1000003], sum;
priority_queue <pair <int, int> > q;
int vis[1000003], inans[1000003], bj[100003];

inline void add(int u, int v, int w)
{
    ver[++cnt] = v, qi[cnt] = u, edge[cnt] = w, nxt[cnt] = head[u], head[u] = cnt;
}

inline void solve(int uuu)
{
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    q.push(make_pair(0, uuu));
    dis[uuu] = 0;
    while (!q.empty())
    {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = nxt[i])
        {
            int v = ver[i], w = edge[i];
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
    memset(bj, 0, sizeof(bj));
    memset(in, 0, sizeof(in));
    for (int i = 1; i <= cnt; i+=1)
    {
        int u = qi[i], v = ver[i], w = edge[i];
        if (dis[u] + w == dis[v])
        {
            bj[i] = 1;
            ++in[v];
        }
    }
    for (int i = 1; i <= cnt; i+=1)
    {
        int u = qi[i], v = ver[i];
        if (bj[i] && in[v] == 1 && u != uuu)
        {
            inans[u] = 1;
        }
    }
}

int main()
{
    n = gi(), m = gi();
    for (int i = 1; i <= m; i++)
    {
        int u = gi(), v = gi(), w = gi();
        add(u, v, w), add(v, u, w);
    }
    for (int i = 1; i <= n; i+=1) solve(i);
    bool fl = true;
    for (int i = 1; i <= n; i+=1)
    {
        if (inans[i]) {fl = false; printf("%d ", i);}
    }
    if (fl) puts("No important cities.");
    return 0;
}

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

原文：https://www.cnblogs.com/xsl19/p/11320488.html