PAT_甲級_1131 Subway Map

テーマ:
無方向図を与えて、1点から別の点までの最短経路を求め、ここでの最短は、起点から終点まで経験した点の数が最も少なく、複数ある場合、出力中継局が最も少ないことを指す.
アルゴリズムの考え方:
最初はDijkstraアルゴリズムでこの問題を解くことを考えていたが、Dijkstraアルゴリズムは第1のスケールが辺権に関する問題を解くのに適していたので、DFSを考え、そのパラメータdepthを設定して、起点から終点までの遍歴過程で経験した結点個数を記録し、その後、グローバル量minDepthを用いて最小のdepthを保存し、中継結点問題であるかどうかを容易に判断するために、隣接マトリクスを使用して、2つの接続点のエッジに対応する回線、例えば2000が2001に接続され、このエッジがLine 4の一部である場合、G[2000][2001]=4;は、乗る最小回線数をグローバル変数$minTranNum$を使用して記録する.
DFS遍歴方法:
DFS関数では現在のノードst,終点e,深さdepthのパラメータを設定し,vector resultを用いて最適なパスを保存し,vector pathは現在のパスを一時的に保存し,まず現在のノード(pathに保存し,アクセスフラグをtrueに設定)にアクセスし,次に終点に到達するか否かを判断し,結果として,まず現在のパスの中継ノード数を計算し,ここでの計算方法は、setセット$diffLines$を使用してすべての回線を追加することであり、そのサイズは乗車する回線数(そのサイズが1つ減少すると中継ノード数)であり、minDepth>depthが現在の経路がより短いことを示す場合、最適経路と最適距離と乗車回線数を更新し、長さが同じであるが乗車する回線が最も少ない場合、では最適経路と乗車路線数を更新し,最後に遡る.終点に到着しなければ、アクセスされていない各ネクタイを再帰的に遍歴し、すべてのネクタイがアクセス済みであれば遡及する.
注意点:

1、クエリーごとにグローバル変数minDepth、minTranNum、visitedを初期化しなければなりません.

2、プログラムにエラーがなく、結果が出力されていない場合は、DFS関数にロールバック操作があるかどうかを確認する(path.pop_back(),visited[st]=false)

送信結果:
ACコード:

#include
#include
#include
#include

using namespace std;

int G[10000][10000];//G[i][j]=4  i j       4    
vector path;//           
vector result;//     
vector Adj[10000];//    
bool visited[10000];

int minDepth;//     
int minTranNum;//         

void DFS(int st, int e, int depth){
    //         
    path.push_back(st);
    visited[st] = true;
    if(st == e){
        //     
        //          
        unordered_set diffLines;//        
        for (int i = 0; i < path.size() - 1; ++i) {
            diffLines.insert(G[path[i]][path[i+1]]);
        }
        if(minDepth>depth){
            //       
            result = path;
            minDepth = depth;
            minTranNum = diffLines.size();
        } else if(minDepth==depth&&minTranNum>diffLines.size()){
            //     ,        
            result = path;
            minTranNum = diffLines.size();
        }
        //   
        path.pop_back();
        visited[st] = false;
        return;
    }
    //         
    for (int next : Adj[st]) {
        //    
        if(!visited[next]){
            DFS(next, e, depth + 1);
        }
    }
    path.pop_back();//   
    visited[st] = false;
}

void print(int start,int end){
    printf("%d
",minDepth);
    int current_line = G[result[0]][result[1]];//     
    int s = start;//          
    for (int i = 1; i < result.size()-1; ++i) {
        if(G[result[i]][result[i+1]]!=current_line){
            // i    
            printf("Take Line#%d from %04d to %04d.
",current_line,s,result[i]);
            s = result[i];
            current_line = G[result[i]][result[i+1]];
        }
    }
    //                     
    printf("Take Line#%d from %04d to %04d.
",current_line,s,end);
}

int main(){
    int N;
    scanf("%d",&N);
    for (int i = 0; i < N; ++i) {
        int M;
        scanf("%d",&M);
        int a,b;
        for (int j = 0; j < M; ++j) {
            if(j==0){
                scanf("%d",&a);
            } else {
                scanf("%d",&b);
                G[a][b] = G[b][a] = i+1;
                Adj[a].push_back(b);
                Adj[b].push_back(a);
                a = b;
            }
        }
    }
    int K;
    scanf("%d",&K);
    int start,end;
    for (int k = 0; k < K; ++k) {
        scanf("%d %d", &start, &end);
        //          
        minDepth = 0x3fffffff;
        minTranNum = 0x3fffffff;
        memset(visited,0, sizeof(visited));
        path.clear();
        result.clear();
        DFS(start, end, 0);
        print(start, end);//       
    }
    return 0;
}