dfs.cpp

#include<iostream>
#include<vector>

#define long long long
#define nln '\n'

using namespace std;

long n, m, s, t;
vector<vector<long>> a;
vector<bool> crs;

void input()
{
    freopen("dfs.inp", "r", stdin);
    //freopen("dfs.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> s >> t;
    a.resize(n+1);
    crs.resize(n+1, 0); // 0 la flase, 1 la true
    for (long i = 1; i <= m; ++i){
        long x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
}

long cnt = 0, miv = 1000000;

void dfs(long u)
{
    if (u == t){
        if (cnt < miv)
            miv = cnt;
        return;
    }
    // Nếu đã đến được đỉnh mục tiêu thì xét xem con đường này đã là ngắn nhất chưa

    for (const auto &i : a[u]){
        // Tìm các đỉnh kề đỉnh u để đi
        // Nếu chưa có thì đi qua và đánh dấu là đã qua, để trên con đường này không đi lại đỉnh đó nữa
        // Sau đó tăng biến cnt là độ dài hay năng lượng tiêu hao trên con đường
        if (!crs[i]){
            crs[i] = 1;
            ++cnt;
            dfs(i); // đi vào đỉnh i
            --cnt;
            crs[i] = 0;
            // sau khi đi qua đỉnh i ta giảm biến cnt đi 1 và đánh dấu là chưa đi qua đỉnh i để đi đường khác
        }
}

int main()
{
    input();
    dfs(s);
    cout << miv << nln;
    // in ra kết quả là năng lượng tiêu hao của con đường ngắn nhất từ đỉnh đầu đến đỉnh cuối
    return 0;
}