比赛 |
20111110 |
评测结果 |
AAAAAAEEEA |
题目名称 |
城市 |
最终得分 |
70 |
用户昵称 |
王者自由 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-11-10 10:13:11 |
显示代码纯文本
#include <cstdio>
#include <cstring>
const int MAXN = 10000, MAXM = 500000;
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;
}