AT_abc277_e 题解

\(\mathcal Solution\)

【题意】

给定无向图，当 \(a_i = 1\) 时，该条边才能走。在给我们 \(k\) 个点，\(S_1, S_2, \cdots, S_k\)，到了这些点可以选择是否取反 \((1 \to 0, 0 \to 1)\) 所有的 \(a_i\)，求 \(1 \to n\) 的最短距离。

【解法】

\(dist_{i, 0}\) 表示到了 \(i\) 这个点且 \(a_i = 0\) 的边可以走的最短距离。

\(dist_{i, 1}\) 表示到了 \(i\) 这个点且 \(a_i = 1\) 的边可以走的最短距离。

则 \(dist_{i, 0} = \min\limits_{s \in g_i}\{dist_{s, 0}+1, [s \in S]dist_{s, 1} + 1\}\)。

则 \(dist_{i, 1} = \min\limits_{s \in g_i}\{dist_{s, 1}+1, [s \in S]dist_{s, 0} + 1\}\)。

其中 \(g_i\) 表示所有 \(i\) 的临边，\(S\) 表示可以取反的点。

\(dist_{i, 0}, dist_{i, 1}\) 都可以用 bfs 求得。

答案 \(= \min\{dist_{n, 0}, dist_{n, 1}\}\) 。

\(\mathcal Code\)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 200010, M = 400010, MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int n, m, k;
PII q[N * 2];
int dist[N][2];
int h[2][N], e[M], ne[M], idx;
unordered_set<int> S;

void add(int h[], int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int s)
{
	memset(dist, 0x3f, sizeof dist);

	int hh = 0, tt = -1;
	dist[s][1] = 0, q[ ++ tt] = {s, 1};
	if (S.count(1)) dist[s][0] = 0, q[ ++ tt] = {s, 0}; // 不要忘了判断 1 是否在集合中
	while (hh <= tt)
	{
		PII t = q[hh ++ ];
		int x = t.x, y = t.y;
		for (int i = h[y][x]; ~i; i = ne[i])
		{
			int j = e[i];
			if (dist[j][y] > dist[x][y] + 1) // 不懂的去看上边的思路
			{
				dist[j][y] = dist[x][y] + 1;
				q[ ++ tt] = {j, y};
			}
			if (S.count(j) && dist[j][y ^ 1] > dist[x][y] + 1)
			{
				dist[j][y ^ 1] = dist[x][y] + 1;
				q[ ++ tt] = {j, y ^ 1};
			}
		}
	}
}

void solve()
{
	memset(h, -1, sizeof h);
	
	cin >> n >> m >> k;
	while (m -- )
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(h[c], a, b), add(h[c], b, a);
	}
	for (int i = 1; i <= k; i ++ )
	{
		int t;
		cin >> t;
		S.insert(t);
	}
	bfs(1);
	
	int res = min(dist[n][0], dist[n][1]); // 求答案
	if (res == INF) res = -1; // 判断无解
	cout << res << endl;
}

int main()
{
	IOS;
	cit, cot;
	int T = 1;
//	cin >> T;
	while (T -- ) solve();
	return 0;
}