题解【洛谷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]重要的城市

题解

代码

最新文章

热门文章