记录编号	411461	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2017-06-05 08:02:25	内存使用	0.57 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 40;

char buf[1<<18],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;}
inline int in(void){
    char tmp = getc();
    int res = 0;
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = (res + (res << 2) << 1) + (tmp ^ 48),
        tmp = getc();
    return res;
}

int N, B1, B2, B3, G1, G2, G3;
int X[MAXN], Y[MAXN];
int f[MAXN][MAXN];
int mi = 0x7fffffff, ans;

int main(){ 
#ifndef LOCAL
    freopen("hopeschool.in", "r", stdin);
    freopen("hopeschool.out", "w", stdout);
#endif
    memset(f, 0x2f, sizeof(f));

    N = in();
    for(int i = 0; i <= N; ++i) f[i][i] = 0;
    B1 = in(), B2 = in(), B3 = in();
    G1 = in(), G2 = in(), G3 = in();
    for(int i = 1; i <= N; ++i) X[i] = in();
    for(int i = 1; i <= N; ++i) Y[i] = in();

    for(int i = 1, k = in(); i <= k; ++i){
        int a = in(), b = in();
        int s1 = in(), s2 = in(), s3 = in();

        f[a][b] = (s1 * B1 + s2 * B2 + s3 * B3) * X[a] + (s1 * G1 + s2 * G2 + s3 * G3) * Y[a];
        f[b][a] = (s1 * B1 + s2 * B3 + s3 * B2) * X[b] + (s1 * G1 + s2 * G3 + s3 * G2) * Y[b];
    }

    for(int k = 1; k <= N; ++k){
        for(int i = 1; i <= N; ++i){
            for(int j = 1; j <= N; ++j){
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    
    for(int i = 1, tmp = 0; i <= N; ++i, tmp = 0){
        for(int j = 1; j <= N; ++j){
            tmp += f[j][i];
        }
        if(mi > tmp) mi = tmp, ans = i;
    }

    printf("%d", ans);
}