dfs

原始文件为 cpp 代码，本文是转换后的 Markdown 文件。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <math.h>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// true == <
bool compare(vector<int>& a, vector<int>& b)
{
    int a_size = a.size();
    int b_size = b.size();
    if(a_size < b_size) return true;
    else if(a_size > b_size) return false;

    for(int i = 0; i < a_size; ++i)
    {
        if(a[i] < b[i]) return true;
        if(a[i] > b[i]) return false;
    }
    return true;
}

vector<int> G[100005];
vector<int> E[100005];
bool vis[100005];

vector<int> best_res;
int best_len;
int n, m; 

void dfs(int cur_node, int cur_len, vector<int>& cur_res);
int main()
{
    // freopen("IDEALPATH.txt", "r", stdin);
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(vis, false, sizeof(vis));
        best_len = n + 5;
        best_res.clear();

        for(int i = 0; i < 100005; ++i) G[i].clear();
        for(int i = 0; i < 100005; ++i) E[i].clear();

        for(int i = 0; i < m; ++i)
        {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            G[u].push_back(v);
            G[v].push_back(u);
            E[u].push_back(c);
            E[v].push_back(c);
        }
        vector<int> result;
        vis[1] = true;
        dfs(1, 0, result);

        printf("%d\n", best_len);

        int size = best_res.size();
        if(size > 0) printf("%d", best_res[0]);
        for(int i = 1; i < size; ++i) printf(" %d", best_res[i]);
        printf("\n");
    }
}

void dfs(int cur_node, int cur_len, vector<int>& cur_res)
{
    // printf("dfs(%d, %d)\n", cur_node, cur_len);
    if(cur_len > best_len) return;

    if(cur_node == n)
    {
        if(cur_len < best_len || compare(cur_res, best_res))
        {
            best_len = cur_len;
            best_res = cur_res;
        }
        return;
    }

    int size = G[cur_node].size();
    for(int i = 0; i < size; ++i)
    {
        int v = G[cur_node][i];

        if(vis[v]) continue;
        vis[v] = true;
        cur_res.push_back(E[cur_node][i]);

        // printf("vis[1] = %d\n", vis[1]);
        // printf("i = %d , dfs(%d, %d) --- dfs(%d, %d)\n", i, cur_node, cur_len, v, cur_len + 1);
        dfs(v, cur_len+1, cur_res);
        vis[v] = false;
        cur_res.pop_back();
    }
}