更好的阅读体验

引用

这题并不是一定要dfs，也可以直接用邻接矩阵判断，但是因为想熟悉一下dfs，所以采用了邻接表这个方法，邻接矩阵的可以参考一下这位大佬的代码

东篱下の悠然 2020年11月28日天梯赛GPLT总决赛（全部题目 + 189分代码答案）

题目描述

一个旅游景点，如果被带火了的话，就被称为“网红点”。大家来网红点游玩，俗称“打卡”。在各个网红点打卡的快（省）乐（钱）方法称为“攻略”。你的任务就是从一大堆攻略中，找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。

样例

输入格式

首先第一行给出两个正整数：网红点的个数 $N(1<N≤200)$ 和网红点之间通路的条数 $ M $ 。随后 $ M $ 行，每行给出有通路的两个网红点、以及这条路上的旅行花费（为正整数），格式为“网红点1 网红点2 费用”，其中网红点从 $ 1 $ 到 $ N $ 编号；同时也给出你家到某些网红点的花费，格式相同，其中你家的编号固定为 0 。

再下一行给出一个正整数 K，是待检验的攻略的数量。随后 K 行，每行给出一条待检攻略，格式为： $n V_1V_2 ⋯ V_n$
​​
其中 $ n(≤200) $ 是攻略中的网红点数，$V_i$ 是路径上的网红点编号。这里假设你从家里出发，从 $V_​1$ 开始打卡，最后从 $V_​n$回家。

输出格式

在第一行输出满足要求的攻略的个数。

在第二行中，首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号（从 1 开始），然后输出这个攻略的总路费，其间以一个空格分隔。如果这样的攻略不唯一，则输出序号最小的那个。

题目保证至少存在一个有效攻略，并且总路费不超过 $10^9$ 。

输入样例

6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

输出样例

3
5 11

样例说明：

第 2、3、4、6 条都不满足攻略的基本要求，即不能做到从家里出发，在每个网红点打卡仅一次，且能回到家里。所以满足条件的攻略有 3 条。

第 1 条攻略的总路费是：(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14；

第 5 条攻略的总路费同理可算得：1 + 1 + 1 + 2 + 3 + 1 + 2 = 11，是一条更省钱的攻略；

第 7 条攻略的总路费同理可算得：2 + 1 + 1 + 2 + 2 + 2 + 1 = 11，与第 5 条花费相同，但序号较大，所以不输出。

算法

(记忆化搜索) $O(n^2)$

这个样例解释有点小坑，反正我是没看出来。它指的每个点不是攻略给出的点，而是1~n个点2333。由题目的意思我们可以知道，只需要dfs搜一下每一个攻略，看看是不是能到终点，并且遍历了n个点，然后记录一下费用和攻略个数即可。

时间复杂度 $O(n)$

鸽了

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210 , M = 100010;

int n , m , k , sum , f;
int INF = 0x3f3f3f3f;

int h[N] , e[N * N] , ne[N * N] , idx;
int path[M] , g[N][N];
long long res[M];
bool st[N];

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}

int dfs(int u , int idx)
{
    //虽然总费用不超过10的9次方，但是int也才2开头的九位数，所以用LL
    long long sum = 0;

    //表示这个点已经被遍历过了
    st[u] = true;

    if(u == 0)
    {
        //标记这个攻略能回到起点
        f = 1;
        return sum;
    }

    //如果当前的点为-1表示不能往下走所以直接返回0；
    if(h[u] ==  -1) return 0;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {   
            //如果这个点没有被遍历过，并且是路线的下一个点，那么就继续走
            if(path[idx] == j) sum += g[u][j] + dfs(j , idx + 1);
        }
    }
    // 返回以u为起点的费用
    return sum;
}

int main()
{

    long long minx = INF;

    cin >> n >> m;

    //初始化头结点和攻略路径
    memset(h , -1 ,sizeof h);
    memset(path , -1 , sizeof path);

    for(int i = 0; i < m; i ++)
    {
        int a , b , c;
        cin >> a >> b >> c;
        //因为这题是无向有环图，所以要加两条边，然后用g记录费用，也就是邻接矩阵
        add(a , b);
        add(b , a);
        g[a][b] = g[b][a] = c;
    }

    cin >> k;

    int cnt = 0;
    for(int i = 0; i < k; i ++)
    {
        int t , flag = 0;
        cin >> t;

        for(int j = 0; j < t; j ++) cin >> path[j];
        //将起点加入路径，作为终点
        path[t] = 0;
        //如果这个点的起点不是零能到的点，那么后续就不需要继续了
        for(int j = h[0]; j != -1; j = ne[j])
            if(e[j] == path[0]) 
                flag = 1;

        if(flag) 
        {
            int t1 = 0;
            //dfs时从攻略的起点开始会好一点
            res[i] += dfs(path[0] , 1) + g[0][path[0]];
            //看一下是否n个点都有且只到过一次
            for(int i = 0; i <= n; i ++) if(st[i]) t1++;
            //如果到了起点并且是n个点都遍历了，那么就更新minx，并且cnt++，n+1是因为包括了0这个点，不这么写也可以
            if(f && t1 == n + 1) minx = min(res[i] , minx) , cnt ++;
            f = 0;
        }

        memset(path , -1 , sizeof path);
        memset(st , 0 , sizeof st);
    }

    cout << cnt << endl;
    //遍历数组看看最先等于minx是哪一个
    for(int i = 0; i < k; i ++)
    {
        if(res[i] == minx)
        {
            cout << i + 1 << ' ' << res[i] << endl;
            break;
        }
    }

    return 0;
}