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

/**
*Prob   : patha
*Data   : 2012-7-10
*Sol    : SPFA+Hash
*/
 
#include <set>
#include <cstdio>
#include <cstring>
 
#define MaxN 3010
#define MaxE 401000
#define oo 20000000
 
using namespace std;
 
//cannot
struct node1 {
    int y,last,next;
} e2[MaxE];
int s[MaxN];
 
//cannot
struct node2 {
    int y,next;
} e[MaxE];
 
int n,m,k,totk=0,tot=0;
int a[MaxN];
bool v[MaxN][MaxN];
int pre[MaxN][MaxN];
int dis[MaxN][MaxN];
struct {
    int x,l;
}list[200000];
 
//从x到y不能到z
void insert(int x,int y,int z) {
    e2[totk].y = z; e2[totk].last = x;
    e2[totk].next = s[y]; s[y] = totk; 
}
void insert1(int x,int y) {
    e[tot].y = y;
    e[tot].next = a[x]; a[x] = tot; 
}
//x到y后能不能到c
bool can(int x,int y,int c)
{
    int tmp = s[y];
    for (;tmp;tmp=e2[tmp].next) {
        if (e2[tmp].last==x&&e2[tmp].y==c)
            return false;
    }
    return true;
}
 
void spfa()
{
    memset(dis,127,sizeof(dis));
    memset(v,false,sizeof(v));
    int open = 1, closd = 0;
    list[1].x = 1; list[1].l = 0;
    dis[0][1] = 0; pre[0][1] = 0;
    v[0][1] = true;
    while (closd<open) {
        int now = list[++closd].x;
        int last = list[closd].l;
        v[last][now] = false;
        int te = a[now];
        for (;te;te=e[te].next) {
            //可以走
            int i = e[te].y;
            if (can(last,now,i)) {
                if (dis[last][now]+1<dis[now][i]) {
                    dis[now][i] = dis[last][now]+1;
                    pre[now][i] = last;
                    if (!v[now][i]) {
                        v[now][i] = false;
                        list[++open].x = i;
                        list[open].l = now;
                    }
                }
            }
        }   
    }
}
 
void print(int x,int y)
{
    if (pre[x][y]!=0) print(pre[x][y],x);
    printf("%d ",x);
}
 
int main()
{
    freopen("patha.in","r",stdin);
    freopen("patha.out","w",stdout);
     
    scanf("%d%d%d",&n,&m,&k);
     
    int x,y,z;
    for (int i=1; i<=m; i++) {
        scanf("%d%d",&x,&y);
        tot++; insert1(x,y);
        tot++; insert1(y,x);
    }
    for (int i=1; i<=k; i++) {
        scanf("%d%d%d",&x,&y,&z);
        totk++; insert(x,y,z);
    }
     
    spfa();
     
    int ans = oo;
    for (int i=1; i<=n; i++) 
        if (dis[i][n]<ans) {
            k = i;
            ans = dis[i][n];
        }
    printf("%d\n",ans);
     
    print(k,n);
    printf("%d\n",n);
     
    fclose(stdin); fclose(stdout); 
    return 0;
}