PAT 1131

题目 ： Subway Map

分值 ： 30
难度 ： 难题
思路 ： DFS深搜
坑点 ： 一开始想K次Dijkstra,发现自己连Dijkstra都卡,后来太慢换成DFS,DFS又找不到感觉了
       简直是无语,真TM菜,菜狗！！！然后DFS好不容易弄出来例程,神他嘛一个点运行超时,我剪
       枝都用了,真的看不出来为什么超时啊！！头疼啊！这题真的日狗,明天继续干他！到底为什
       么会超时啊,别人的DFS我也看了,甚至觉的还是我的快一点啊，为什么超时！！烦人！

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <vector>
using namespace std;
vector< vector<int>> v(10000);
vector<int> path ;
vector<int> result;
int line[10000][10000];
int cnt= 0 ,cnt_tansfer ;
int pre_line ;
int min_cnt = 9999 ,min_tansfer = 9999;
int flag[10000];
int S,D ;
void Dfs(int s ,int d)
{
    if(cnt> min_cnt ||   cnt == min_cnt && min_tansfer < cnt_tansfer)
        return ;
    if(s ==d )
    {
        if(cnt < min_cnt || cnt == min_cnt && min_tansfer > cnt_tansfer )
        {
            min_cnt = cnt ;
            min_tansfer = cnt_tansfer ;
            result = path ;
        }
        return ;
    }
    for(int i = 0 ; i < v[s].size() ; i++)
    {
        if(flag[ v[s][i] ] ) continue ;
        int old = cnt_tansfer ;
        int old_prime = pre_line ;

        int temp_line = line[s][v[s][i]];
        if(temp_line != pre_line)
            cnt_tansfer ++ ;
        pre_line = temp_line ;
        flag[ v[s][i] ] =1 ;
        cnt++ ;
        path.push_back(v[s][i]) ;

        Dfs( v[s][i] , d) ;

        cnt--;
        cnt_tansfer = old ;
        pre_line = old_prime;
        flag[ v[s][i] ] =0 ;
        path.pop_back() ;
    }
}
int main()
{
    int N , M ,pre;
    scanf("%d",&N);
    for(int i = 1 ; i<= N ;i++)
    {
        //cin >> M >> pre ;
        scanf("%d%d",&M ,& pre) ;
        for(int j = 1 ; j < M ; j++)
        {
            int temp ;
            scanf("%d",&temp) ;
            //cin >> temp;
            v[temp].push_back(pre) ;
            v[pre].push_back(temp) ;
            line [temp][pre] = line[pre][temp] = i ;
            pre = temp ;
        }
    }
    int K ;
    scanf("%d",&K);
    for(int i = 0 ; i< K ; i++)
    {
        scanf("%d%d",&S,&D);
        cnt = 0 ;
        min_cnt = 9999;
        min_tansfer = 9999;
        path.clear();
        result.clear();
        path.push_back(S );
        Dfs(S,D);
        printf("%d\n",min_cnt);
        int start = 0 ;
        int old_line = 0 ;
        int now_line ;
        for(int i = 1 ; i< result.size() ;i++)
        {
            now_line = line[result[i-1]][result[i]] ;
            if(now_line != old_line)
            {
                if(old_line)
                {
                    printf("Take Line#%d from %04d to %04d.\n", old_line ,result[start] ,result[i-1] );
                    start =i-1;
                }
                old_line = now_line ;
            }
        }
        printf("Take Line#%d from %04d to %04d.\n", now_line ,result[start] ,result[result.size()-1] );
    }
}