L2-036 网红点打卡攻略

传送门

解题思路

这题主要是对题意的理解，代码实现不难

题目要我们求出 从起点到终点再到起点的攻略，其中，每个网红打卡点只能经过一次 ， 并且终点到起点必须是通的（因为不能原路返回）

对于每个攻略，只需要逐个检查就行，如果上一个点到这个点是通的并且这个点没出现过，该点有效，让这条攻略的总花费加上该边的花费。

因此，需要一个bool数组做标记 ， 由于数据很小，建邻接矩阵（显然不是邻接表） ， 无向图，如果有效，就放进答案数组里。由于最后要知道最小花费对应的攻略编号，可以采用哈希表（题目保证最优解唯一）来记录不同编号对应的花费。

注意：

哈希表遍历的时候，可以修改value值，但是无法修改key值。

#include<iostream>
#include<unordered_map>
#include<cstring>
using namespace std;
int e[210][210];
bool vis[210];
unordered_map<int,int> ans;
int main()
{
    int n,m;cin>>n>>m;
    int cnt = 0;
    while(m--)
        {
            int l,r,d;cin>>l>>r>>d;
            e[l][r] = d;
            e[r][l] = d;
        }
    int k;cin>>k;
    for(int i = 1 ; i <= k ; i++)
        {
            memset(vis,0,sizeof vis);
            int sum = 0 ;
            int num ; cin>>num;
            int ori = 0 ;
            vis[0] = true;
            bool suc = true;
            for(int j = 1 ; j <= num ; j++)
                {
                    int cur;cin>>cur;
                    if(vis[cur]) suc = false;
                    if(e[ori][cur])
                    {
                         sum += e[ori][cur];
                         vis[cur] = true; 
                         ori = cur;
                     
                    }
                    else suc = false;
                    if(j == num && e[ori][0] == 0) suc= false; //不能原路返回，因为只能打卡一次
                    else if(j == num) sum += e[ori][0];
                    
                }
            
            for(int j = 1; j <= n ; j++)
                {
                    if(!vis[j])
                    {
                        suc = false;
                        // cout<<"序号"<<i<<" "<<suc;
                        break;
                    }
                }
            if(suc) ans[i] = sum,cnt++;
            
        }
    int mn = 2e9;
    int choice ;
    for(int i = 1 ; i <= k ; i++)
        {
            if(ans[i] && ans[i] < mn)
            {
                mn = ans[i];
                choice = i;
            }
        }
    cout<<cnt<<endl<<choice<<" "<<mn<<endl;
    return 0;
}