P1371（C++题解）

解题思路:
暴力搜索加最优化剪枝
注意事项:不想填（滑稽）

参考代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int mid[10];
int n,m,q;
int E[10],F[10];
int x,y,z,d;
int lin[105],cnt;
struct str
{
    int next,y,z,d;
}e[10005];
void insertt()
{
    e[++cnt].y=y;
    e[cnt].next=lin[x];
    lin[x]=cnt;
    e[cnt].z=z;
    e[cnt].d=d;
}
int vis[105];
int ans,temp;
void work(int x)
{
    if(x==n-1)
    {
        ans=ans>temp?temp:ans;
        return ;
    }
    if(temp>=ans)return ;
    for(int i=lin[x];i;i=e[i].next)
    {
        if(!vis[e[i].y])
        {
            vis[e[i].y]=1;
            temp+=e[i].d;
            int tt=++mid[e[i].z];
            if(tt==2)temp+=E[e[i].z];
            else if(tt>2)temp+=F[e[i].z];
            work(e[i].y);
            if(tt==2)temp-=E[e[i].z];
            else if(tt>2)temp-=F[e[i].z];
            --mid[e[i].z];
            vis[e[i].y]=0;
            temp-=e[i].d;
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&q)!=EOF)
    {
        cnt=0;
        memset(e,0,sizeof(e));
        memset(lin,0,sizeof(lin));
        memset(mid,0,sizeof(mid));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<m;i++)
            scanf("%d",&E[i]);
        for(int i=0;i<m;i++)
            scanf("%d",&F[i]);
        for(int i=0;i<q;i++)
        {
            scanf("%d%d%d%d",&x,&y,&z,&d);
            insertt();
        }
        ans=2000000000;
        temp=0;
        work(0);
        printf("%d\n",ans);
    }
    return 0;
}