#include <iostream>
#include <cstdio>
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;
typedef long long LL;
struct E {
    int to;
    int next;
    LL cost;
    E() {}
    E(int a, LL b):to(a),cost(b) {}
};
const int maxn = 1100000;
const int oo = 0xffffffff;
int head[2*maxn];
E edge[6*maxn];
LL dist[2*maxn];
bool vis[2*maxn];
int n, eid = 1;

inline void addEdge(int from, int to, LL cost) {
    edge[eid].to = to;
    edge[eid].cost = cost;
    edge[eid].next = head[from];
    head[from] = eid ++;
}
//
//struct node {
//    int to;
//    LL dis;
//    node() {}
//    node(int a, LL b) {
//        to = a, dis = b;
//    }
//    bool operator < (const node& other) const {
//        return dis > other.dis;
//    }
//};

//void dijkstra_heap(int s) {
//    for (int i = 0; i <= 2 * n + 1; i ++) {
//        dist[i] = -1;
//        vis[i] = false;
//    }
//    priority_queue<node> que;
//    dist[s] = 0;
//    que.push(node(s, 0));
//    while (!que.empty()) {
//        node cur = que.top();
//        que.pop();
//        int from = cur.to;
//        if(vis[from]) {
//            continue;
//        }
//        vis[from] = true;
//        for (int i = head[from]; ~i; i = edge[i].next) {
//            int to = edge[i].to;
//            if(!vis[to] && dist[to] == -1 || dist[to] > dist[from] + edge[i].cost) {
//                dist[to] = dist[from] + edge[i].cost;
//                que.push(node(to, dist[to]));
//            }
//        }
//    }
//}
void spfa_slf(int s) {
    deque<int> que;
    for (int i = 0; i <= 2 * n + 1; i++) {
        dist[i] = oo;
        vis[i] = 0;
    }
    dist[s] = 0;
    vis[s] = 1;
    que.push_back(s);
    while (!que.empty()) {
        int cur = que.front();
        que.pop_front();
        vis[cur] = 0;
        for (int j = head[cur]; j != -1; j = edge[j].next) {
            int e = edge[j].to;
            if(dist[e] == oo || dist[e] > dist[cur] + edge[j].cost) {
                dist[e] = dist[cur] + edge[j].cost;
                if(!vis[e]) {
                    vis[e] = 1;
                    if(!que.empty()) {
                        if(dist[e] > dist[que.front()]) {
                            que.push_back(e);
                        } else {
                            que.push_front(e);
                        }
                    } else {
                        que.push_back(e);
                    }
                }
            }
        }
    }
}
int dir[2] = {0};
int main() {
    int x, y, st, ed;
    LL dis;
    while (scanf("%d", &n) != EOF, n) {
        dir[1] = n + 1;
        scanf("%d%d", &x, &y);
        st = y  + dir[x];
        scanf("%d%d", &x, &y);
        ed = y  + dir[x];
        fill(head, head + 2 * n + 2, -1);
        for (int i = 0; i < n; i ++) {
            scanf("%I64d", &dis);
            addEdge(i, i + 1, dis);
            addEdge(i + 1, i, dis);
        }
        for (int i = 0; i <= n; i ++) {
            scanf("%I64d", &dis);
            addEdge(i, i + n + 1, dis);
            addEdge(i + n + 1, i, dis);
        }
        for (int i = n + 1; i < 2 * n + 1; i ++) {
            scanf("%I64d", &dis);
            addEdge(i, i + 1, dis);
            addEdge(i + 1, i, dis);
        }
//        dijkstra_heap(st);
        spfa_slf(st);
        printf("%I64d\n", dist[ed]);
    }
}

• heap....... (0) shinelin 2015-12-01 21:56:13