P1811

本人用 map 判三元组 + dijkstra 写，但是 WA #3 求助。。。

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

int n,m,k;
vector<int> mp[3005];
map<tuple<int, int, int>, bool> ok;

int dis[3005],las[3005],ans[3005];
bool vis[3005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;

void dijkstra()
{
	for(int i = 1;i <= n;i++)dis[i] = inf;
	dis[1] = 0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = 0;i < (int)mp[u].size();i++)
		{
			int v = mp[u][i];
			if(ok[{las[u],u,v}])continue;
			if(dis[u] + 1 < dis[v])
			{
				dis[v] = dis[u] + 1;
				las[v] = u;
				q.push(make_pair(dis[v],v));
			}
		}
	}
	return;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	while(m--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	while(k--)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		ok[{u,v,w}] = 1;
	}
	dijkstra();
	
	printf("%d\n",dis[n]);
	int now = 1;
	for(int i = n;i;i = las[i])
	{
		ans[now++] = i;
	}
	while(--now)
	{
		printf("%d ",ans[now]);
	}
	return 0;
}