记录编号	443741	评测结果	AWAAA
题目名称	[HAOI 2005]希望小学	最终得分	80
用户昵称	_WA自动机	是否通过	未通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-08-31 23:27:23	内存使用	0.31 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<climits>
using namespace std;
int n,b1,b2,b3,g1,g2,g3,k,x[31],y[31],dis[31][31],num,head[101];
bool vis[31];
struct Edge
{
    int dis,to,next;
}edge[101];

void add(int from,int to,int dis)
{
    edge[++num].next=head[from];
    edge[num].dis=dis;
    edge[num].to=to;
    head[from]=num;
}

void spfa(int v)
{
    queue<int> q;
    q.push(v);
    vis[v]=1;dis[v][v]=0;
    while(!q.empty())
    {
        int now=q.front();q.pop();vis[now]=0;
        for (int i=head[now];i;i=edge[i].next)
        {
            if (dis[v][now]+edge[i].dis<dis[v][edge[i].to])
            {
                dis[v][edge[i].to]=dis[v][now]+edge[i].dis;
                if (!vis[edge[i].to])
                {
                    q.push(edge[i].to);
                    vis[edge[i].to]=1;
                }
            }
        }
    }
}

int main()
{
    #ifndef COGS
    freopen("hopeschool.in","r",stdin);
    freopen("hopeschool.out","w",stdout);
    #endif // COGS
    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d%d%d%d%d%d",&n,&b1,&b2,&b3,&g1,&g2,&g3);
    for (int i=1;i<=n;++i)
    {
        scanf("%d",x+i);
    }
    for (int i=1;i<=n;++i)
    {
        scanf("%d",y+i);
    }
    scanf("%d",&k);
    for (int i=1;i<=k;++i)
    {
        int ai,bi,si1,si2,si3;
        scanf("%d%d%d%d%d",&ai,&bi,&si1,&si2,&si3);
        int least1=INT_MAX,least2=INT_MAX;
        least1=si1*(x[ai]*b1+y[ai]*g1)+si2*(x[ai]*b2+y[ai]*g2)+si3*(x[ai]*b3+y[ai]*g3);
        add(ai,bi,least1);
        least2=si1*(x[bi]*b1+y[bi]*g1)+si2*(x[bi]*b2+y[bi]*g2)+si3*(x[bi]*b3+y[bi]*g3);
        add(bi,ai,least2);
    }
    for (int i=1;i<=n;++i)
    spfa(i);
    int MIN=INT_MAX,pos;
    for (int i=1;i<=n;++i)
    {
        int ans=0;
        for (int j=1;j<=n;++j)
        {
            if (dis[j][i]!=0x3f3f3f3f)
            ans+=dis[j][i];
        }
        if (ans<MIN) {MIN=ans;pos=i;}
    }
    printf("%d\n",pos);
    return 0;
}
/********************我怎么还没有凑够100行******************************
/********************我怎么还没有凑够100行******************************
/********************我怎么还没有凑够100行******************************
/********************我怎么还没有凑够100行******************************
/********************我怎么还没有凑够100行******************************
/********************我怎么还没有凑够100行******************************
/********************我怎么还没有凑够100行******************************
/********************我怎么还没有凑够100行******************************
/********************我怎么还没有凑够100行******************************
/********************我怎么还没有凑够100行******************************
/**************************好了，够了***********************************/