输出最短路径

//输出两个顶点间的最短路径
//利用dfs递归寻找两点间路径
//利用vector<int>存储路径并在遍历到终点顶点时输出路径

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e5;

int n,m,k,pre[N];
bool st[N];
int s, t;
vector<int> path;

struct Node{
    int val;
    Node* next;
    Node(int _val):val(_val),next(NULL){}
}* head[N];

void add(int a, int b){
    Node *p = new Node(b);
    p -> next = head[a];
    head[a] = p;
}

void dfs(int s, int t){

    if(s == t){//找到终点，输出Path
        for(auto x: path) {
            cout << x << " ";
        }
        cout << ";" << endl;
        return;
    }

    for(auto p = head[s]; p; p = p -> next){
        int i = p -> val;
        if(!st[i]){
            st[i] = true;
            path.push_back(i);
            dfs(i, t);//递归路径上的每个结点到终点的路径
            path.pop_back();
            st[i] = false;
        }
    }
}

int main(){
    cin >> n >> m >> k;
    int a, b;

    for(int i = 1; i <= m; i++){
        cin >> a >> b;
        add(a,b);
    }

    while(k--){
        cin >> s >> t;
        st[s] = true;
        path.push_back(s);//将起点输入到路径中
        printf("%d -> %d的路径有：",s,t);
        dfs(s, t);
        st[s] = false;
        path.pop_back();//还原现场
        cout << endl;
    }

    return 0;
}