PTA——L2-4 网红点打卡攻略 (25 分)

本质上就是一个链式前向星建图加一个简单地查找（注意这里是双向图），没什么太大的难点，但是样例中的第四条路线过不了（但是我感觉是可行的），所以代码无法处理第四条路线这样的数据。

using namespace std;
int n,m;//点个数和路径条数
int x,y,z;//点1,点2，费用
int cnt,k,cost;//k行攻略
int mp[600];
long long ans;
struct point{
    int t,next,co;
}edge[2000];
int head[500];

void addedge(int x,int y,int z){
    edge[++cnt].t=y;
    edge[cnt].co=z;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
struct anss{//输出答案的
    int a,b;
};
deque<int> route;
queue<anss> fina;
void searh(int x){
    int flag=-1,nt;//nt是下一个点
    //  cout<<x;
    for(int i=head[x]; i!=-1; i=edge[i].next){
        //cout<<route.front();
        if(edge[i].t==route.front()){
            flag=1;
            nt=route.front();
            route.pop_front();
            cost+=edge[i].co;
            //cout<<9;
            break;
        }
        //cout<<edge[i].t;
    }
    
    if(flag==-1){
        for(int i=head[route.front()]; i!=-1; i=edge[i].next){
            if(edge[i].t==x){
                flag=-1;
                nt=route.front();
                route.pop_front();
                cost+=edge[i].co;
                break;
            }
        }
    }
    
    if(flag==1&&!route.empty())
    searh(nt);
    else
        return;
}
int main(){
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1; i<=m; i++){
        cin>>x>>y>>z;
        addedge(x,y,z);
        addedge(y,x,z);
    }
    cin>>k;
    int flag;
    int cont=0,cntt=0,l;
    for(int i=1; i<=k; i++){
        memset(mp,0,sizeof(mp));
        flag=1;
        while(!route.empty())
            route.pop_front();
        ans=1e9;
        cost=0;
        cin>>cont;
       
        while(cont--){
            cin>>l;
            if(mp[l]==1)
                flag=-1;
            mp[l]=1;
            route.push_back(l);
        } 
        route.push_back(0);
        if(flag==1)
        searh(0);
        if(route.empty()){
           cntt++;
            if(cost<ans){
                ans=cost;
                anss dd;
                dd.a=i;
                dd.b=cost;
                fina.push(dd);
            }
        }
    }
    
    cout<<cntt<<endl;
    int po=1e9,a;
    while(!fina.empty()){
        if(fina.front().b<po){
            po=fina.front().b;
            a=fina.front().a;
        }
            fina.pop();
     }
    cout<<a<<" "<<po;
    return 0;
}