P 1078文化の旅
タイトルリンク
検索しました.しかし、中間にspfaのような緩和最適化を加えた.データは水のようです.
検索しました.しかし、中間にspfaのような緩和最適化を加えた.データは水のようです.
#include
#include
#include
#include
#include
using namespace std;
const int M=107*107;
int n,m,s,t,k;
int b[109][109],c[109];
int vis[101];
int ans=1e9;
int dis[109][109],st[109],top;
int d[109];
void dfs(int u,int cost)
{
if(cost>=ans) return;
if(u==t)
{
if(ans>cost) ans=cost;
return;
}
for(int j=1;j<=n;j++)
if(!vis[j]&&cost+dis[u][j]dis[u][j]+cost)
{
int flag=0;
for(int i=1;i<=top;i++)
if(vis[st[i]]&&b[c[j]][c[st[i]]])
{
flag=1;
break;
}
if(flag) continue;
d[j]=dis[u][j]+cost;
vis[j]=1;
st[++top]=j;
dfs(j,cost+dis[u][j]);
vis[j]=0;
top--;
}
}
int main()
{
//freopen("a.txt","r",stdin);
memset(dis,127/3,sizeof(dis));
memset(d,127/3,sizeof(d));
scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=k;i++) b[i][i]=1;
for(int i=1;i<=m;i++)
{
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
dis[u][v]=min(d,dis[u][v]);
dis[v][u]=min(d,dis[v][u]);
}
//memset(vis,0,sizeof(vis));
vis[s]=1;st[++top]=s;d[s]=1;
dfs(s,0);
if(ans!=1e9) printf("%d",ans);
else printf("-1
");
return 0;
}