問題 D: 文化之旅
時間限制: 1 Sec 記憶體限制: 128 MB
題目描述
有一位使者要游歷各國，他每到一個國家，都能學到一種文化，但他不愿意學習任何一種文化超過一次（即如果他學習了某種文化，則他就不能到達其他有這種文化的國家），不同的國家可能有相同的文化，不同文化的國家對其他文化的看法不同，有些文化會排斥外來文化（即如果他學習了某種文化，則他不能到達排斥這種文化的其他國家），
現給定各個國家間的地理關系，各個國家的文化，每種文化對其他文化的看法，以及這位使者游歷的起點和終點（在起點和終點也會學習當地的文化），國家間的道路距離，試求從起點到終點最少需走多少路，
輸入
第一行為五個整數 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），
樣例輸入 Copy
2 2 1 1 2
1 2
0 1
1 0
1 2 10
樣例輸出 Copy
-1
提示
對于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，
flody演算法求最短路，n<=100范圍很小，暴力即可
代碼如下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;
int n,k,m,s,t;
int c[N],a[N][N],mp[N][N];
int main()
{
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>>a[i][j];
for(int i = 1; i<=n; i++)
for(int j = 1; j<=n; j++)
{
if(i!=j)
mp[i][j]=99999999;
}
while(m--)
{
int u,v,d;
cin>>u>>v>>d;
if(!a[c[u]][c[v]])mp[u][v]=min(mp[u][v],d);
if(!a[c[v]][c[u]])mp[v][u]=min(mp[v][u],d);
}
for(int k = 1; k<=n; k++)//flody,k為中間國，用來松弛
for(int i = 1; i<=n; i++)
for(int j = 1; j<=n; j++)
{
if(!a[c[i]][c[k]]&&!a[c[i]][c[j]]&&!a[c[k]][c[j]])
{
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
}
if(mp[s][t]==99999999)cout<<-1;
else cout<<mp[s][t];
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258514.html
標籤：其他