- 1#include 2#include 3#include 4#include 5#include 6#include 7#define maxn 150000 8#define LL long long 9 10 using namespace std;
- 11 LL n,
- m,
- u,
- v,
- s;
- 12 13 struct Edge 14 {
- 15 LL next,
- to,
- w;
- 16
- };
- 17 struct Edge edge[maxn];
- 18 LL cnt = 0;
- 19 LL head[maxn];
- 20 LL val[maxn];
- 21 22 void add(LL u, LL v, LL ww) 23 {
- 24 edge[++cnt].to = v;
- 25 edge[cnt].w = ww;
- 26 edge[cnt].next = head[u];
- 27 head[u] = cnt;
- 28
- }
- 29 30 deque q; //双向队列
- 31 LL book[maxn],
- dis[maxn];
- 32 33 int spfa(LL x) //最大的价值
- 34 {
- 35
- if (val[u] > x || val[v] > x) return 0; //剪枝
- 36 memset(book, 0, sizeof(book));
- 37 38
- for (LL i = 1; i <= n; i++) 39 dis[i] = 1e12;
- 40 41 book[u] = 1;
- dis[u] = 0;
- 42 q.push_back(u);
- 43 44
- while (!q.empty()) 45 {
- 46 LL fr = q.front();
- 47 book[fr] = 0;
- q.pop_front();
- 48
- for (LL i = head[fr]; i; i = edge[i].next) 49 {
- 50 LL j = edge[i].to;
- 51
- if (val[j] > x) continue;
- 52
- if (dis[j] > dis[fr] + edge[i].w) 53 {
- 54 dis[j] = dis[fr] + edge[i].w;
- 55
- if (!book[j]) 56 {
- 57
- if (q.empty()) q.push_back(j);
- 58
- else 59 {
- 60
- if (dis[j] < dis[q.front()]) 61 q.push_front(j); //在前部插入
- 62
- else 63 q.push_back(j);
- 64
- }
- 65 book[j] = 1; //标记已经入队
- 66
- }
- 67
- }
- 68
- }
- 69
- }
- 70
- if (dis[v] <= s) return 1;
- 71
- return 0;
- 72
- }
- 73 74 75 int main() 76 {
- LL l = 1,
- r = 0;
- 77 cin >> n >> m >> u >> v >> s;
- 78
- for (LL i = 1; i <= n; i++) 79 {
- 80 cin >> val[i];
- 81 r = max(val[i], r);
- 82
- }
- 83 LL t1,
- t2,
- t3;
- 84
- for (LL i = 1; i <= m; i++) 85 {
- 86 cin >> t1 >> t2 >> t3;
- 87 add(t1, t2, t3);
- 88 add(t2, t1, t3);
- 89
- }
- 90
- if (!spfa(1e13)) 91 {
- 92 cout << -1;
- 93
- return 0;
- 94
- }
- 95
- while (l <= r) 96 {
- 97 LL mid = (l + r) >> 1;
- 98
- if (spfa(mid)) r = mid - 1;
- 99
- else l = mid + 1;
- 100
- }
- 101 cout < endl;
- 102
- return 0;
- 103
- }
来源: http://www.bubuko.com/infodetail-2083907.html