记录编号	33337	评测结果	AAAAAATEEA
题目名称	城市	最终得分	70
用户昵称	王者自由	是否通过	未通过
代码语言	C++	运行时间	1.395 s
提交时间	2011-11-10 12:57:54	内存使用	12.59 MiB

#include <cstdio>
#include <cstring>
const int MAXN = 10000, MAXM = 800000;
struct map {
    int y, x, d;
} G[MAXM];
int n, m, u, v, s, t;
int a[MAXN], fir[MAXN], c[MAXN];
bool b[MAXN];
int q[MAXM], head, tail;
int x, y, d, min = 0x7fffffff, max;
bool SP(int g) {
    if(a[u] > g) return true;
    memset(b, false, sizeof(b));
    memset(c, 100, sizeof(c));
    c[q[1] = u] = 0, b[u] = true;
    head = 0, tail = 1;
    while(head < tail) {
        t = fir[q[++head]];
        while(t > 0) {
            if(a[G[t].y] > g) {
                t = G[t].x;
                continue;
            }
            if(c[q[head]] + G[t].d < c[G[t].y]) {
                c[G[t].y] = c[q[head]] + G[t].d;
                if(!b[G[t].y]) {
                    b[G[t].y] = true;
                    q[++tail] = G[t].y;
                }
            }
            t = G[t].x;
        }
        b[q[head]] = false;
    }
    if(c[v] > s) return true; else return false;
}
int main() {
    freopen("cost.in","r",stdin);
    freopen("cost.out","w",stdout);
    scanf("%d %d %d %d %d", &n, &m, &u, &v, &s);
    for(int i=1; i<=n; i++) {
        scanf("%d", &a[i]);
        if(a[i] > max) max = a[i];
        if(a[i] < min) min = a[i];
    }
    for(int i=1; i<=m; i++) {
        scanf("%d %d %d", &x, &y, &d);
        t++;
        G[t].y = y, G[t].x = fir[x], G[t].d = d;
        fir[x] = t;
        t++;
        G[t].y = x, G[t].x = fir[y], G[t].d = d;
        fir[y] = t;
    }
    if(SP(max))
        printf("-1\n");
    else {
        int l = min, r = max, p;
        while(l < r) {
            p = (l + r) / 2;
            if(!SP(p)) r = p; else l = p + 1;
        }
        printf("%d\n", l);
    }
    return 0;
}