AcWing 452. 文化之旅
原题链接
困难
作者:
liyx19
,
2020-10-04 09:05:06
,
所有人可见
,
阅读 432
Dijistra O(n^2)
#include<iostream>
#include<cstring>
using namespace std;
const int N=105;
int a[N][N],cul[N],g[N][N],dist[N],st[N],cst[N];//cst用于记录自己已学的文化
bool check(int j){//判断这个国家的文化是否排斥自己
for(int i=1;i<=N;i++){
if(cst[i]){
if(a[j][cst[i]]) return false;
}
}
return true;
}
int main(){
int n,k,m,s,e;
cin>>n>>k>>m>>s>>e;
for(int i=1;i<=n;i++){
cin>>cul[i];
}
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
cin>>a[i][j];
}
}
memset(g,0x3f,sizeof g);
memset(dist,0x3f,sizeof dist);
for(int i=1;i<=m;i++){
int u,v,d;
cin>>u>>v>>d;
g[u][v]=g[v][u]=min(g[u][v],d);//重边的问题
}
dist[s]=0;
cst[cul[s]]=1;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dist[j]<dist[t]) && check(j))
t=j;
}
st[t]=1;
cst[cul[t]]=1;
if(t==-1){
cout<<-1;
return 0;
}
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
if(dist[e]==0x3f3f3f3f) cout<<-1;
else cout<<dist[e];
}
同学,泥试试这组样例:
应该输出-1吧
同学,你注意一下你那个程序的开头,好像有一点点怪异,ACwing出错了,你最好重新提交一下……
好的谢谢您
没事没事