1.题号:NC16577

2.题目:

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。
现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。
输入描述:
第一行为五个整数N，K，M，S，T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为 1 到N），文化种数（文化编号为 1 到 K），道路的条数，以及起点和终点的编号（保证S 不等于T）；
第二行为N个整数，每两个整数之间用一个空格隔开，其中第i个数Ci，表示国家i的文化为Ci。
接下来的K行，每行K个整数，每两个整数之间用一个空格隔开，记第i行的第j个数为 aij，aij= 1 表示文化 i 排斥外来文化 j（i 等于 j 时表示排斥相同文化的外来人），aij= 0 表示不排斥（注意i 排斥 j 并不保证 j 一定也排斥i）。
接下来的M行，每行三个整数u，v，d，每两个整数之间用一个空格隔开，表示国家u与国家v有一条距离为d的可双向通行的道路（保证u不等于v，两个国家之间可能有多条道路）。
输出描述:
输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出-1）。

3.链接:链接：https://ac.nowcoder.com/acm/problem/16577

4.思路:

将文化冲突的国家的距离提前设置为无穷即可
原本想用堆优化版的dijkstra算法，但发现是稠密图，用朴素版的更好
写代码需注意，忘记写输入了，找了半天错误
补充：该题解存在问题，去洛谷上试发现AC不了，仅当记录.(用bitset存储学习的文化似乎能过)

5.代码:

using namespace std;
typedef pair<int,int> PII;
const int N = 1e4+9;
const int MAXN = 110;
/*
int h[N],e[N],ne[N],idx,w[N];
int n,k,m,s,t;
int c[MAXN];
int a[MAXN][MAXN];
int dist[N];
bool vis[N];
map<int,int> mp;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int Dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,s});
    while(q.size())
    {
        auto t=q.top();
        int id=t.second,distance=t.first;
        q.pop();
        if(vis[id]) continue;
        vis[id]=true;
        for(int i=h[id];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                q.push({j,dist[j]});
            }
        }
    }
    return dist[t];
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>k>>m>>s>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        mp[c[i]]=0;
    }
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=k;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    int t=Dijkstra();
    if(t>0x3f3f3f3f/2) cout<<-1;
    else cout<<t;
    return 0;
}
*/

int map[MAXN][MAXN],g[MAXN][MAXN];
int c[N];
int dist[MAXN];
bool st[MAXN];
int vis[MAXN][MAXN];
int n,k,m,s,t;
int main()
{
    memset(g,0x3f,sizeof g);
    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 a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
        g[b][a]=min(g[b][a],c);
    }
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vis[c[i]][c[j]]==1) g[i][j]=0x3f3f3f3f;
        }
    }
    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            while(!st[j]&&(t==-1||dist[j]<dist[t]))
                t=j;
        st[t]=true;
        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    if(dist[t]>0x3f3f3f3f/2) cout<<-1;
    else cout<<dist[t];
    return 0;
}

题解 | #文化之旅#

1.题号:NC16577

2.题目:

3.链接:链接：https://ac.nowcoder.com/acm/problem/16577

4.思路:

5.代码: