CF59E-link

重题P1811

本地连样例都跑炸。。。

#include <bits/stdc++.h>
#define re register int
#define mt(a, b, c) make_tuple(a, b, c)
using namespace std;
typedef tuple<int, int, int> tiii;
const int N = 3e3 + 10, M = 4e4 + 10;
struct edge
{
	int to, next;
}e[M];
struct part
{
	int pre, now, dis;
}p[N];
int top, h[N], road[N];
int n, m, k;
bool vis[M];
queue<part> q;
map<tiii, bool> mp;

void add(int x, int y)
{
	e[++ top] = (edge){y, h[x]};
	h[x] = top;
}

void print(int x)
{
	if (road[x]) print(road[x]);
	cout << x << ' ';
}

void bfs()
{
	q.push((part){0, 1, 0});
	while (!q.empty())
	{
		part x = q.front(); q.pop();
		if (x.now == n)
		{
			cout << x.dis << '\n';
			print(n);
			exit(0);
		}
		
		for (re i = h[x.now]; i; i = e[i].next)
		{
			int y = e[i].to;
			if (vis[i] || mp[ mt(x.pre, x.now, y)]) continue;
			vis[i] = true;
			road[y] = x.now;
			q.push((part){x.now, y, x.dis + 1});
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> k;
	for (re i = 1; i <= m; i ++)
	{
		int x, y;
		cin >> x >> y;
		add(x, y); add(y, x);
	}
	for (re i = 1; i <= k; i ++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		mp[ mt(a, b, c) ] = true;
	}
	bfs();
	//cout << "-1"; p1811
	
	return 0;
}