描述
有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习任何一种文化超过一次,即如果他学习了某种文化,则他就不能到达其他有这种文化的国家。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同,有些文化会排斥外来文化,即如果他学习了某种文化,则他不能到达排斥这种文化的其他国家。 现给定各个国家间的地理关系,各个国家的文化,每种文化对其他文化的看法,以及这位使者游历的起点和终点(在起点和终点也会学习当地的文化),国家间的道路距离,试求从起点到终点最少需走多少路。
输入
第一行为五个整数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,两个国家之间可能有多条道路。
对于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≤N^2,1≤ki≤K,1≤u,v≤N,1≤d≤1000,S≠T,1≤S,T≤N。
输出
输出只有一行,一个整数,表示使者从起点国家到达终点国家最少需要走的距离数,如果无解则输出-1。
样例输入
2 2 1 1 2
1 2
0 1
1 0
1 2 10
样例输出
-1
题意
每个国家有一种文化,使者在一个国家会学习当地的文化,使者不会去他已经学过的文化的国家,问从S到T的最短路是多少
题解
floyd先不考虑文化问题处理出d[i][j]的最短路
在dfs搜所有路径,如果当前到u的距离dis+最短的u到终点T>=ans,说明这条路径不行了
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=105; 5 int N,K,M,S,T,u,v,w,ans; 6 int a[maxn][maxn],d[maxn][maxn],G[maxn][maxn],c[maxn]; 7 bool vis[maxn]; 8 9 void dfs(int u,int dis) 10 { 11 if(dis+d[u][T]>=ans)return; 12 if(u==T) 13 { 14 ans=min(ans,dis); 15 return; 16 } 17 for(int v=1;v<=N;v++) 18 { 19 if(!a[c[v]][c[u]]&&!vis[c[v]]) 20 { 21 vis[c[v]]=true; 22 dfs(v,dis+G[u][v]); 23 vis[c[v]]=false; 24 } 25 } 26 } 27 int main() 28 { 29 memset(d,0x3f3f3f3f,sizeof d); 30 memset(G,0x3f3f3f3f,sizeof G); 31 scanf("%d%d%d%d%d",&N,&K,&M,&S,&T); 32 for(int i=1;i<=N;i++) 33 scanf("%d",&c[i]),G[i][i]=d[i][i]=0; 34 for(int i=1;i<=K;i++) 35 for(int j=1;j<=K;j++) 36 scanf("%d",&a[i][j]); 37 for(int i=1;i<=M;i++) 38 { 39 scanf("%d%d%d",&u,&v,&w); 40 if(!a[c[u]][c[v]]&&c[u]!=c[v])G[v][u]=d[v][u]=min(d[v][u],w); 41 if(!a[c[v]][c[u]]&&c[u]!=c[v])G[u][v]=d[u][v]=min(d[u][v],w); 42 } 43 for(int k=1;k<=N;k++) 44 for(int i=1;i<=N;i++) 45 for(int j=1;j<=N;j++) 46 if(!a[c[k]][c[i]]&&!a[c[j]][c[k]]&&d[i][j]>d[i][k]+d[k][j]) 47 d[i][j]=d[i][k]+d[k][j]; 48 memset(vis,false,sizeof vis); 49 ans=0x3f3f3f3f; 50 vis[c[S]]=true; 51 dfs(S,0); 52 if(ans==0x3f3f3f3f)printf("-1 "); 53 else printf("%d ",ans); 54 return 0; 55 }