code1316 文化之旅

文化之旅的本质是最短路问题，只不过添加了一个文化排斥，仅需要做最短路时判断一下是否排斥即可

因为数据较小，采用了Floyd算法，以下是代码，关键部分附注释：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define Size 105 
using namespace std;

int N,K,M,S,T;
int G[Size][Size];//邻接矩阵
int c[Size];//c[i]表示第i个国家的文化
bool against[Size][Size];//如果a排斥b，against[a][b]=1,反之为0

bool chack(int a,int b){//判断国家a与b是否排斥
    return against[c[a]][c[b]];
}

void input(){
    cin>>N>>K>>M>>S>>T;
    
    for(int i=1;i<=N;i++){
        cin>>c[i];
    }
    
    for(int i=1;i<=K;i++){//一开始写成<=N，结果...
        for(int j=1;j<=K;j++){
            cin>>against[i][j];
        } 
    }
    
    int a,b,v;
    for(int i=1;i<=M;i++){
        cin>>a>>b>>v;
        if(!chack(b,a))G[a][b]=v;//如果b排斥a，则即使a与b之间有路也不能走,G[a][b]=0x3f3f3f3f(见初始化)。反之，就赋值为道路长度v
        if(!chack(a,b))G[b][a]=v;//同上。
    }
}

void Folyd(){
    for(int k=1;k<=N;k++){
        for(int a=1;a<=N;a++){
            if(a==k || chack(k,a))continue;//注意判断是否排斥。因为a->k，要保证k不排斥a，所以chack(k,a),不要写反了
            for(int b=1;b<=N;b++){
                if(b==a||b==k || chack(b,a)||chack(b,k))continue;//同上
                G[a][b]=min(G[a][b], G[a][k]+G[k][b]);//因为初始化时G就被赋为最大值，所以无需判断a,k,b之间是否有路。直接取最小值即可
            }
        }
    }
}

int main(){
    memset(G,0x3f,sizeof(G));
    
    input();
    
    Folyd();
    
    if(G[S][T]>=0x3f3f3f3f)cout<<-1;
    else cout<<G[S][T];
    
    return 0;
}