记录编号	39400	评测结果	AAAAAAAAAA
题目名称	866.三元限制最短路	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.415 s
提交时间	2012-07-10 12:03:20	内存使用	48.43 MiB

#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
typedef unsigned short int usint;
const int MAXN=3003;
const usint INF=65500;
int N,M,K;
vector<int> map[MAXN];
int pre[MAXN][MAXN];

class Funou{public:int a,b,c;};
class cmp
{
public:
	bool operator() (const Funou&a,const Funou&b)
	{
		if(a.a!=b.a) return a.a<b.a;
		if(a.b!=b.b) return a.b<b.b;
		return a.c<b.c;
	}
};
set<Funou,cmp> Fhash;
set<Funou,cmp> :: iterator iter;
bool flag[MAXN][MAXN];
usint dist[MAXN][MAXN];
class Queue
{
public:
	int mae,now;
};
queue<Queue> q;

inline void init()
{
	int a,b,c;
	scanf("%d %d %d\n",&N,&M,&K);
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d\n",&a,&b);
		map[a].push_back(b);
		map[b].push_back(a);
	}
	for(int i=1;i<=K;i++)
	{
		scanf("%d %d %d",&a,&b,&c);
		Fhash.insert((Funou){a,b,c});
	}
}

inline void bfs()
{
	for(int i=1;i<=N;i++) 
		for(int j=1;j<=N;j++)
			flag[i][j]=0,dist[i][j]=INF;
	dist[0][1]=0; flag[0][1]=1;
	q.push((Queue){0,1});
	Queue tmp;
	int tm,tp,tv,np;
	while(q.size())
	{
		tmp=q.front(); q.pop();
		tm=tmp.mae,tp=tmp.now; tv=dist[tm][tp];
		for(unsigned int i=0;i<map[tp].size();i++)
		{
			np=map[tp][i]; if(flag[tp][np]) continue;
			if(Fhash.find((Funou){tm,tp,np})!=Fhash.end()) continue;
			flag[tp][np]=1; dist[tp][np]=tv+1; q.push((Queue){tp,np});
			pre[tp][np]=tm;
		}
	}
}

inline void output()
{
	int now,ans=INF;
	for(int i=1;i<=N;i++) 
		if(dist[i][N]<ans && Fhash.find((Funou){pre[i][N],i,N})==Fhash.end())
			ans=dist[i][N],now=i;
	printf("%d\n",ans); int top=2;
	int num[MAXN]; num[1]=N; num[2]=now;
	while(now!=1)
	{
		now=pre[num[top]][num[top-1]];
		num[++top]=now;
	}
	for(int i=top;i>=1;i--) printf("%d ",num[i]);
}

int main()
{
	freopen("patha.in","r",stdin);
	freopen("patha.out","w",stdout);
	init();
	bfs();
	output();
	return 0;
}