POJ 2457 Part Acquisition

第一反应是BFS,比较直观，但是输出路径写的不是很熟练，此外，习惯不好，“==”写成了“=”，所以常量一定放前面！

 1 #include <cstdio>
 2 #include <queue>
 3 #include <cstring>
 4 using namespace std;
 5 int N, K;
 6 typedef struct node
 7 {
 8     int in, out;
 9     int pos;
10 }Link;
11 const int maxn = 50005;
12 bool vis[maxn];
13 Link A[maxn];
14 int pre[maxn], B[maxn];
15
16 int main(void) {
17     freopen("in.txt", "r", stdin);
18     freopen("out.txt", "w", stdout);
19     scanf("%d%d", &N, &K);
20     memset(vis, false, sizeof(vis));
21     queue<Link> Q;
22     for (int i = 0; i < N; i++) {
23         scanf("%d%d", &A[i].in, &A[i].out);
24         A[i].pos = i;
25         if (A[i].in == 1) {
26             pre[i] = -1;
27             vis[i] = true;
28             Q.push(A[i]);
29         }
30     }
31
32     if (K == 1) {
33         printf("1\n1\n");
34     } else {
35         if (Q.empty()) {
36             printf("-1\n");
37         } else {
38             while (!Q.empty()) {
39                 Link front = Q.front();
40                 if (front.out == K) {
41                     break;
42                 }
43                 for (int i = 0; i < N; i++) {
44                     if (!vis[i] && A[i].in == front.out) {
45                         Q.push(A[i]);
46                         vis[i] = true;
47                         pre[i] = front.pos;
48                     }
49                 }
50                 Q.pop();
51
52             }
53             if (Q.empty()) {
54                 printf("-1\n");
55             } else {
56                 int cnt = 0;
57                 int i = Q.front().pos;
58                 for (;-1 != pre[i];) {
59                     B[cnt++] = A[i].out;
60                     i = A[pre[i]].pos;
61                 }
62                 B[cnt++] = A[i].out;
63
64                 printf("%d\n1\n", cnt+1);
65                 for (int k = cnt-1; k >= 0; k--) {
66                     printf("%d\n", B[k]);
67                 }
68             }
69         }
70     }
71
72 }

View Code

看到别人用SPFA、dijkstra,有时间也试一试！

【待写】