Link: https://ac.nowcoder.com/acm/problem/16577
Source: niuke.com

Title Description
There is a messenger who wants to travel around countries. Every time he goes to a country, he can learn a culture, but he is unwilling to learn any culture more than once (that is, if he learns a culture, he can't reach other countries with this culture). Different countries may have the same culture. Countries with different cultures have different views on other cultures. Some cultures will exclude foreign cultures (that is, if he learns a certain culture, he cannot reach other countries that exclude this culture).

Given the geographical relationship between countries, the culture of each country, the views of each culture on other cultures, as well as the starting point and end point of the envoy's tour (he will also learn the local culture at the starting point and end point), the road distance between countries, try to find out the minimum distance to go from the starting point to the end.

Enter Description:
The first line consists of five integers N, K, M, S and T, separated by a space between each two integers, which successively represent the number of countries (country number is 1 to N), the number of cultural species (culture number is 1 to k), the number of roads, and the numbers of starting and ending points (ensure that S is not equal to t);

The second line is N integers, and every two integers are separated by a space. The ith number CI indicates that the culture of country i is Ci.

In the next K lines, there are k integers in each line, and every two integers are separated by a space. Note that the number of J in line i is aij, aij= 1 indicates that culture i excludes foreign culture J (when i is equal to j, it excludes outsiders of the same culture), and aij= 0 indicates no exclusion (note that i excluding J does not guarantee that J will also exclude i).

In the next M line, there are three integers u, v and d in each line. Every two integers are separated by a space, indicating that there is a bidirectional road with a distance of d between Country U and country v (ensure that u is not equal to v, and there may be multiple roads between two countries).

Output Description:
The output has only one line and an integer, indicating the minimum distance that the messenger needs to travel from the starting country to the destination country (if there is no solution, output - 1).
Example 1
input
copy

2 2 1 1 2
1 2
0 1
1 0
1 2 10

output
copy

-1

explain
Since country 2 must pass through country 1, and the civilization of country 2 excludes the civilization of country 1, it is impossible to reach country 2.
Example 2
input
copy

2 2 1 1 2
1 2
0 1
0 0
1 2 10

output
copy

10

explain
The route is 1 - > 2
Problem solving ideas:
Solution 1: dfs()

1. Use vis [] [] to store mutually exclusive cultures, and visit [] [] to mark whether the culture of the country has been visited.
   2) According to vis[i][c[s]]=1, it can be judged that visit[i]=1; Countries that show I these cultures cannot be visited
   3) Find the shortest path by dfs() on the basis of meeting the requirements of the problem.
   c + + code

#include <bits/stdc++.h>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,k,m,s,t,ans=100000000,cnt=0;
int c[200];
int vis[200][200];
int visit[200];
struct node
{
    int to,next,w;
}e[20000];
int head[200];
void addedge(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;

}
void dfs(int s,int step)//Depth search for the shortest path
{

    int flag=0;
    if(s==t) ans=min(ans,step) ;
    visit[c[s]]=1;
    for(int i=1;i<=k;i++)//Indicates that the marked culture will exclude s's culture and does not need access
       if(vis[i][c[s]]) visit[i]=1;
    for(int i=head[s];i;i=e[i].next)
    {
        if(!visit[c[e[i].to])
        {
            flag=1,dfs(e[i].to,step+e[i].w);
        }
    }
    if(!flag) visit[c[s]]=0;//If s culture has not been used, it should be released, and the culture excluded by s culture should also be released
    for(int i=1;i<=k;i++)
    {
        if(vis[c[s]][i]) visit[i]=0;
    }
}
int main()
{

    cin>>n>>k>>m>>s>>t;
    for(int i=1;i<=n;i++)
        cin>>c[i];
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
        cin>>vis[i][j];
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
        addedge(v,u,w);
    }
    dfs(s,0);
    if(ans==100000000) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

Solution 2:
floyed algorithm makes the distance between S and t the shortest by performing n^2 relaxation operations on each node. In the process of judgment, the judgment of excluding cultural countries is added at the same time.
c + + code

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
//FLOYED

int yy[105][105];
int c[105];
int dist[105][105];
int n,k,m,s,t;
void floyed()
{
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
              if(dist[i][k]+dist[k][j]<dist[i][j]&&!yy[c[i]][c[k]]&&!yy[c[k]][c[j]]&&c[i]!=c[k]&&c[k]!=c[j])
    {
        dist[i][j]=dist[i][k]+dist[k][j];
    }
}
int main()
{
    memset(dist,0x3f3f3f3f,sizeof(dist));
    cin>>n>>k>>m>>s>>t;
    for(int i=1;i<=n;i++)
        cin>>c[i];
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
        cin>>yy[i][j];
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        dist[u][v]=w;
        dist[v][u]=w;
    }
    floyed();
    if(dist[s][t]>=0x3f3f3f3f)
        cout<<-1<<endl;
    else
        cout<<dist[s][t]<<endl;
    return 0;

}