记录编号	39412	评测结果	AAAAAAAAAA
题目名称	866.三元限制最短路	最终得分	100
用户昵称	CC	是否通过	通过
代码语言	C++	运行时间	0.425 s
提交时间	2012-07-10 15:19:24	内存使用	111.01 MiB

#include <cstdio> 
#include <algorithm> 
#include <cstring> 
#include <map> 
#define INF 1000000000 
struct edge { 
    int y; 
    edge *next; 
    edge (int y,edge *next): y(y),next(next) {}; 
}*a[20],*no[3001][3001]; 
struct pp { 
    int u,v; 
}; 
using namespace std; 
int n,m,K,dist,before; 
int num,dis[3001][3001],pre[3001][3001],ans[3001];
pp q[1000000]; 
void spfa() {  
    int head = 0,tail = 0; 
    memset(dis,61,sizeof(dis)); 
    q[0].u = 0; 
    q[0].v = 1; 
    dis[0][1] = 0; 
    pre[0][1] = 0; 
    bool bu; 
    while (head <= tail) { 
        int u = q[head].u,v = q[head++].v; 
        for (edge *p = a[v];p;p = p->next) { 
            bu = 0; 
            for (edge *t = no[u][v];t;t = t->next) { 
                if (p->y == t->y) bu = 1; 
            } 
            if (bu) continue; 
            if (dis[v][p->y] > dis[u][v] + 1) { 
                dis[v][p->y] = dis[u][v] + 1; 
                pp e; 
                e.u = v;e.v = p->y; 
                pre[v][p->y] = u; 
                q[++tail] = e; 
            } 
        } 
    } 
} 
  
int main() { 
    freopen("patha.in","r",stdin); 
    freopen("patha.out","w",stdout); 
    scanf("%d%d%d", &n, &m, &K); 
    int p,q,r; 
    for (int i = 1;i <= m;i++) { 
        scanf("%d%d", &p, &q); 
        a[p] = new edge(q,a[p]); 
        a[q] = new edge(p,a[q]); 
    } 
    for (int i = 1;i <= K;i++) { 
        scanf("%d%d%d", &p, &q, &r); 
        no[p][q] = new edge(r,no[p][q]); 
    } 
    spfa(); 
    dist = INF; 
    for (int i = 1;i <= n;i++) if (dis[i][n] < dist) { 
        dist = dis[i][n]; 
        before = i; 
    } 
    printf("%d\n", dist); 
    ans[dist + 1] = n;ans[dist] = before; 
    num = dist; 
    for (int i = pre[before][n];i != 0;i = pre[before][i]) { 
        ans[--dist] = i; 
        int tmp = before; 
        before = i; 
        i = tmp; 
    } 
    for (int i = 1;i <= num + 1;i++) printf("%d ", ans[i]); 
    return 0; 
}