记录编号	41677	评测结果	AAAAAAAAAA
题目名称	[東方S2] 伊吹萃香	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.105 s
提交时间	2012-08-08 21:42:31	内存使用	0.58 MiB

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 5000*2 + 10;
int n, m, d[N];
vector<int> G[N], c[N];
bool l[N];
void Ins(int u, int v, int k) {
    G[u].push_back(v);
    c[u].push_back(k);
}
void Bellman(int s) {
    memset(d, 15, sizeof(d));
    queue<int> q;
    d[s] = 0; q.push(s); l[s] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop(); l[u] = 0;
        for(int i=0; i<G[u].size(); i++) {
            int v = G[u][i];
            if(d[v] > d[u] + c[u][i]) {
                d[v] = d[u] + c[u][i];
                if(!l[v]) {
                    l[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
int main() {
    freopen("suika.in", "r", stdin);
    freopen("suika.out", "w", stdout);
    scanf("%d %d", &n, &m);
    int p[N], w[N], s[N];
    for(int i=1; i<=n; i++)
        scanf("%d", p+i);
    for(int i=1; i<=n; i++)
        scanf("%d", w+i);
    for(int i=1; i<=n; i++)
        scanf("%d", s+i);
    for(int i=1; i<=n; i++) {
        Ins(i*2, i*2-1, 0);
        Ins(i*2-1, i*2, s[i]);
    }
    for(int i=1; i<=m; i++) {
        int u, v, k;
        scanf("%d %d %d", &u, &v, &k);
        if(p[u] == p[v]) {
            Ins(u*2-1, v*2, k);
            Ins(u*2, v*2-1, k);
        } else {
            Ins(u*2-1, v*2-1, k + abs(w[u] - w[v]));
            Ins(u*2, v*2, max(k - abs(w[u] - w[v]), 0));
        }
    }
    Bellman(2 - p[1]);
    printf("%d\n", min(d[n*2], d[n*2-1]));
    return 0;
}