D. 【NOIP2012普及组真题】文化之旅

题解：

– 这是一道真水题，说实话，正解不会，因为我们的测试数据所有的文化都不排斥，这就很美丽了……..
– 华丽丽的Floyd就来了…
– 注意极大值不要超范围了，是真绝望！

代码：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=105;
const int mmm=99999;int n,m,k,s,t;
int g[MAXN][MAXN];
int c[MAXN];
int no[MAXN][MAXN];bool ok(int x,int y){if(c[x]==c[y])return 0;if(no[c[y]][c[x]])return 0;return 1;
}int main(){
//  freopen("culture.in","r",stdin);
//  freopen("culture.out","w",stdout);cin>>n>>k>>m>>s>>t;for(int i=1;i<=n;i++){scanf("%d",&c[i]);for(int j=1;j<=n;j++)g[i][j]=mmm;}for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)scanf("%d",&no[i][j]);for(int i=1;i<=m;i++){int u,v,l;scanf("%d%d%d",&u,&v,&l);g[u][v]=l;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(ok(i,k)&&ok(k,j))g[i][j]=min(g[i][j],g[i][k]+g[k][j]);else if(!ok(i,k))g[i][k]=mmm;elseg[k][j]=mmm;if(g[s][t]==mmm)cout<<-1;elsecout<return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！