题目描述

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

输入描述:

第一行为五个整数N，K，M，S，T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为 1 到N），文化种数（文化编号为 1 到 K），道路的条数，以及起点和终点的编号（保证S 不等于T）；
第二行为N个整数，每两个整数之间用一个空格隔开，其中第i个数，表示国家i的文化为。
接下来的K行，每行K个整数，每两个整数之间用一个空格隔开，记第i行的第j个数为 ， 表示文化 i 排斥外来文化 j（i 等于 j 时表示排斥相同文化的外来人）， 表示不排斥（注意i 排斥 j 并不保证 j 一定也排斥i）。
接下来的M行，每行三个整数u，v，d，每两个整数之间用一个空格隔开，表示国家u与国家v有一条距离为d的可双向通行的道路（保证u不等于v，两个国家之间可能有多条道路）。

输出描述:

输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出-1）。

示例1

输入
2 2 1 1 2
1 2
0 1
1 0
1 2 10
输出
-1
说明
由于到国家2必须要经过国家1，而国家2的文明却排斥国家1的文明，所以不可能到达国家2。

示例2

输入
2 2 1 1 2
1 2
0 1
0 0
1 2 10
输出
10
说明
路线为1->2

备注:

对于20%的数据，有2≤N≤8，K≤5；
对于30%的数据，有2≤N≤10，K≤5；
对于50%的数据，有2≤N≤20，K≤8；
对于70%的数据，有2≤N≤100，K≤10；
对于100%的数据，有2≤N≤100，1≤K≤100，1≤M≤N2，1≤ki≤K，1≤u,v≤N，1≤d≤1000，S≠T，1 ≤S, T≤N。

解答

首先说一下什么叫单源最短路径问题：
给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。（摘自百科）
这个题算是正儿八经的单源最短路径问题，因为图中边上的权值不可能为负值，所以采用dijkstra算法：
dijkstra算法采用贪心策略，下面进行图解


准备：我们需要一个b数组作为一个集合用来表示已经达到最优的点，b[i]=0表示编号为i的点在集合外；
一个dis数组表示距离，dis【i】表示出发点到i的最短距离，dis初始化为-1；
1，b【1】=1（1到1距离为0，已达到最优），然后从出发点点1开始找到目标点能到达的点2,3并更新dis数组；
从中选择距离出发点最近的点3（即从b数组为0，d值最小且不为0的点中选一个点）；
2，b【3】=1，从能从3到达的b【i】=0的点中进行下一步操作；分两种情况，dis为-1和不为-1；如点5的dis值为-1，辣么d[5]=map[5][3]+d[3]=10+1=11; 如dis[2]=4,dis[2]=min(dis[2],map[2][3],+d[3])=min(4,5)=4;
目的就是利用第1，步找到的距离目标点最近的点来尝试优化当前的路径；
3，从b数组为0，d值最小且不为0的点中选一个点（1,3 b数组值已为1），选出点2；
4，重复第二步b【2】=1；
从能从3到达的b【i】=0的点中进行下一步操作；分两种情况，dis为-1和不为-1；如点4的dis值为-1，辣么d[4]=map[4][2]+d[2]=2+4=6; 如dis[5]=11,dis[5]=min(dis[5],map[2][5],+d[2])=min(11,1+4)=5;
直到所有的点b数组值为1，输出dis数组就是初始点到每一个点的最近路径长度

参考代码： 
#include<cstring>  
#include<cmath>  
#include<iostream>  
#include<climits>  
using namespace std;  
const int L=110;  
int C[L],vis[L][L],map[L][L],dis[L];// 文化值数组，文化是否冲突数组 地图  出发点到每个点的最短距离数组   
bool b[L]; // 点是否最优判断数组   
int main(){  
    memset(map,0,sizeof(map));  
    int N,K,M,S,T;  
    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 n=1;n<=K;n++)cin>>vis[i][n];  
    for(int i=1;i<=M;i++){  
        int x,y,d;  
        cin>>x>>y>>d;  
        map[x][y]=d;  
        map[y][x]=d;  
    }  
    memset(dis,-1,sizeof(dis));  
    //数据初始化  
    for(int i=1;i<=N;i++){  
        if(i==S)dis[i]=0;  
        else if(map[S][i]!=0){  
            if(vis[C[i]][C[S]]==0)dis[i]=map[S][i];//初始化   
        }  
    }  
    b[S]=1;// 初始化   
    for(int i=1;i<N-1;i++){  
        int xmin=INT_MAX,k=-1;  
        for(int n=1;n<=N;n++)if(!b[n]&&xmin>dis[n]&&dis[n]!=-1){  
            xmin=dis[n];  
            k=n; //挑出的最近的点   
        }  
        if(k==-1)continue;  
        //利用挑出的点进行优化   
        b[k]=1;  
        for(int n=1;n<=N;n++)if(!b[n]&&map[n][k]!=0&&vis[C[n]][C[k]]==0){  
            if(dis[n]==-1)dis[n]=dis[k]+map[n][k];  
            else dis[n]=min(dis[n],dis[k]+map[n][k]);  
        }  
    }  
    cout<<dis[T];  
    return 0;  
}


来源：蓝色如烟