JDOJ 1788

https://neooj.com/oldoj/problem.php?id=1788

题面请点连接，全是图太麻烦....................

题挺简单，可以用floyd和dijkstra算法，dij更快一些，强力推荐。

所以代码：

#include<bits/stdc++.h>
using namespace std;
int z[150],n,k,m;
int from,want,s[120][120],q[120][120]; 
int ans=9999999,may,have[120];
void search(int now)
{
    int i,j;
    if(now==want)
    {
        if(may<ans) ans=may;
        return ;
    }
    if(may>=ans) return ;
    for(i=1;i<=n;i++)
    {
        if(q[now][i]!=9999999&&z[have[i]]==0)
        {
            may+=q[now][i];
            z[have[i]]=-1;
            for(j=1;j<=n;j++)
                if(s[have[j]][i]) z[j]++;
            search(i);
            may-=q[now][i];
            z[have[i]]=0;
            for(j=1;j<=n;j++)
                if(s[have[j]][i]) z[j]--;
        }
    } 
}
int main()
{
    int a,b,c,j,i;
    memset(z,0,120);
    scanf("%d%d%d%d%d",&n,&k,&m,&want,&from);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&have[i]);
        for(j=1;j<=n;j++)
            q[i][j]=9999999;
    }
    for(i=1;i<=k;i++)
        for(j=1;j<=k;j++)
        {
            s[i][j]=false;
            scanf("%d",&b);
            if(!b)continue;
            s[i][j]=true;        
        }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(q[a][b]>c) q[a][b]=c; 
        if(q[b][a]>c) q[b][a]=c;
    } 
    z[have[from]]=-1;
    for(i=1;i<=n;i++)
        if(s[i][have[from]]) z[i]++;
    search(from);
    if(ans==9999999) ans=-1;
    printf("%d",ans);
    return 0; 
}