NC16577. [NOIP2012]文化之旅
描述
有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。
现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。
输入描述
第一行为五个整数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，两个国家之间可能有多条道路）。
输出描述
输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出-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->2C++14(g++5.4) 解法, 执行用时: 12ms, 内存消耗: 480K, 提交时间: 2018-10-05 19:59:14
#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,t,c[110],cant[110][110],map1[110][110];
int main()
{
for(int i=0;i<=107;i++)
{
for(int j=0;j<=107;j++)
map1[i][j]=10000000;
}
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 j=1;j<=k;j++)
{
cin>>cant[i][j];
}
}
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
if(cant[c[v]][c[u]]==0&&c[u]!=c[v])
{
map1[u][v]=min(map1[u][v],w);
}
if(cant[c[u]][c[v]]==0&&c[u]!=c[v])
{
map1[v][u]=min(map1[v][u],w);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{ for(int k=1;k<=n;k++)
{
if(c[i]!=c[j]&&c[j]!=c[k]&&c[k]!=c[i]&&map1[i][j]>map1[i][k]+map1[k][j])
{
map1[i][j]=map1[i][k]+map1[k][j];
}
}
}
}
if(map1[s][t]==10000000)
cout<<-1;
else
cout<<map1[s][t];
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 8ms, 内存消耗: 504K, 提交时间: 2022-10-14 13:31:28
#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,k,m,s,t,nn[105],gay[105][105],f[105][105];
int main()
{
int aa,bb,cc;
cin>>n>>k>>m>>s>>t;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)f[i][j]=0xfffffff;
for(int i=1;i<=n;i++)cin>>nn[i];
if(nn[s]==nn[t])
{
cout<<-1;
return 0;
}
for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)cin>>gay[i][j];
for(int i=1;i<=m;i++)
{
cin>>aa>>bb>>cc;
if(gay[nn[bb]][nn[aa]]==0&&nn[aa]!=nn[bb])f[aa][bb]=min(f[aa][bb],cc);
if(gay[nn[aa]][nn[bb]]==0&&nn[aa]!=nn[bb])f[bb][aa]=min(f[bb][aa],cc);
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)if(f[j][i]!=0xfffffff&&f[i][j]!=0xfffffff&&f[j][i]+f[i][k]<f[j][k])f[j][k]=f[j][i]+f[i][k];
if(f[s][t]!=0xfffffff)cout<<f[s][t];
else cout<<-1;
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 7ms, 内存消耗: 1232K, 提交时间: 2022-10-16 11:58:20
#include<bits/stdc++.h>
using namespace std;
long long n,k,m,s,t,i,j,x,y,z,p[500][500],a[500][500],w[500];
int main(){
cin>>n>>k>>m>>s>>t;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)a[i][j]=INT_MAX;
for(i=1;i<=n;i++)cin>>w[i];
for(i=1;i<=k;i++)for(j=1;j<=k;j++)cin>>p[i][j];
for(i=1;i<=m;i++){
cin>>x>>y>>z;
if(z<a[x][y]){
if(p[w[x]][w[y]]==0)a[y][x]=z;
if(p[w[y]][w[x]]==0)a[x][y]=z;
}
}
for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i][k]+a[k][j]<a[i][j]) a[i][j]=a[i][k]+a[k][j];
if(a[s][t]==INT_MAX)cout<<-1;
else cout<<a[s][t];
}