admin管理员组文章数量:1644430
#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
const int MAX_N = 101;
const int INF = 16843009;
int N,K,M,S,T;
int C[MAX_N];
int G[MAX_N][MAX_N];
int R[MAX_N][MAX_N];
int dist[MAX_N];
bool Inqueue[MAX_N];
bool gone[MAX_N];
struct node
{
bool culture[MAX_N];
int country;
};
struct node head,next;
queue<struct node> Q;
int ans = INF;
void SPFA()
{
int i;
int v;
int u;
for (i=1;i<=K;i++)
head.culture[i]=false;
head.country = T;
memset(dist,1,sizeof(dist));
memset(Inqueue,false,sizeof(Inqueue));
dist[T]=0;
Inqueue[T]=true;
head.culture[T]=true;
Q.push(head);
while (!Q.empty())
{
head=Q.front();
Q.pop();
v=head.country;
Inqueue[v]=false;
for (u=1;u<=N;u++)
if (G[u][v])
{
next=head;
next.country = u;
bool flag = true;
for (i=1;i<=N;i++)
if (head.culture[i]&&R[C[i]][C[u]]) flag = false;
if (head.culture[u]) flag = false;
if (C[T]==C[u]&&T!=u) flag = false;
if (dist[v]+G[u][v]>=dist[u]) flag = false;
if (!flag) continue;
dist[u]=dist[v]+G[u][v];
if (!Inqueue[u])
{
Inqueue[u]=true;
next.culture[u]=true;
Q.push(next);
}
}
}
}
void init()
{
int i,j;
int s,t,w;
scanf("%d %d %d %d %d",&N,&K,&M,&S,&T);
for (i=1;i<=N;i++)
scanf("%d",&C[i]);
for (i=1;i<=K;i++)
for (j=1;j<=K;j++)
scanf("%d",&R[i][j]);
for (i=1;i<=M;i++)
{
scanf("%d %d %d",&s,&t,&w);
G[s][t]=(G[s][t]!=0)?min(G[s][t],w):w;
G[t][s]=(G[t][s]!=0)?min(G[t][s],w):w;
}
SPFA();
memset(gone,false,sizeof(gone));
gone[S]=true;
}
int work(int country,int value)
{
int i,j;
bool flag;
if (value+dist[country]>=ans) return 0;
if (country==T)
{
ans = min(ans,value);
return 0;
}
for (i=1;i<=N;i++)
if (G[country][i])
{
flag = true;
for (j=1;j<=N;j++)
if (gone[j]&&R[C[i]][C[j]]) flag = false;
if (C[i]==C[T]&&i!=T) flag = false;
if (gone[i]) flag = false;
if (!flag) continue;
gone[i]=true;
work(i,value+G[country][i]);
gone[i]=false;
}
return 0;
}
void put()
{
if (ans==INF) ans=-1;
printf("%d",ans);
}
int main()
{
freopen("culture.in","r",stdin);
freopen("culture.out","w",stdout);
init();
work(S,0);
put();
return 0;
}
版权声明:本文标题:culture文化之旅 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1729377772a1199038.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论