这是2017年的冬天。（又到了白色相簿的季节2333）
滑完雪之后，ことり突然想吃点心啦！于是她去了甜品店。
日本的冬天经常下雪。不幸的是，今天也是这样，每秒钟雪的厚度会增加q毫米。
秋叶原共有n个地点，编号从1到n。每个地点在开始的时候的积雪高度为hi。
有m条双向道路连接这些地点，它们的长度分别为wi米。
雪太大，公共交通系统已经停摆了，所以ことり得走路回家。她走路的速度是1m/s。
为了方便地图的绘制，秋叶原的道路规划使得每条道路严格地连接两个不同的地点，并且不会有两条道路连接的地点相同。
每个地点都有一个极限雪高li，单位是毫米，如果到达这个地点的时候，这里的雪的高度高于li则会被困在这个点走不出去，无法成功地走到ことり家。
点心店这个地点的编号是s，ことり家的编号是t。
不考虑点心店和ことり家的雪。
ことり想在g秒内回到家吃点心，越快越好。如果在g秒之内，ことり无法到家，或者她被困在路上了，那么ことり会把wtnap变成她的点心( ? 8 ? )
输入格式：
第1行6个整数，空格隔开，分别代表n，m，s，t，g，q。
以下n行，每行2个整数，空格隔开，分别表示这个地点的hi和li。
以下m行，每行3个整数，空格隔开，分别表示这条路连接的两个地点u, v和这条路的长度wi。
输出格式：
输出1行1个整数，表示到达ことり家的最短用时。
如果wtnap变成了ことり的点心那么输出"wtnap wa kotori no oyatsu desu!"
输出时不含引号。
输入样例#1:
2 1 1 2 10 1
1 10
3 10
1 2 6
输出样例#1:
6
输入样例#2:
5 6 2 5 10 1
1 10
1 10
1 10
1 10
1 10
1 5 9
1 3 9
2 4 1
2 5 9
3 4 1
3 5 6
输出样例#2:
8
输入样例#3:
5 6 2 5 10 1
1 10
1 10
10 10
1 10
1 10
1 5 9
1 3 9
2 4 1
2 5 11
3 4 1
3 5 6
输出样例#3:
wtnap wa kotori no oyatsu desu!
对于0%的数据，与样例一模一样；
对于40%的数据，q = 0。
对于上一行中50%的数据，所有wi < li。
对于100%的数据，1 ≤ s, t ≤ n; 0 ≤ g, q ≤ 10^9; 0 ≤ wi ≤ li ≤ 10^9。
Dijkstra，每次弹出dist值最小的顶点后，若该顶点不可达(dist值*q > 限高 - 初始高度)，则不扩展其邻接点。
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
#define NO_VALUE -1
typedef long long LL;
struct AdjNode {
int adj_v;
int adj_weight;
AdjNode(int adj_v, int adj_weight) : adj_v(adj_v), adj_weight(adj_weight) {}
};
class Dijkstra {
public:
bool dijkstra(vector<AdjNode> *graph, int nv, int src, int des, int q, LL * v_height, LL *p_shortest_dist);
private:
struct PriorityNode {
int v;
LL dist;
PriorityNode(int v, LL dist) : v(v), dist(dist) {}
};
struct cmp {
bool operator() (PriorityNode& a, PriorityNode& b) {
return a.dist > b.dist;
}
};
LL * dist_;
bool * collected_;
priority_queue<PriorityNode, vector<PriorityNode>, cmp> pq_;
};
bool Dijkstra::dijkstra(vector<AdjNode>* graph, int nv, int src, int des, int q, LL * v_height, LL * p_shortest_dist) {
dist_ = new LL[nv];
fill(dist_, dist_ + nv, NO_VALUE);
collected_ = new bool[nv];
fill(collected_, collected_ + nv, false);
dist_[src] = 0;
pq_.push(PriorityNode(src, 0));
int top_v, adj_v;
LL tmp_dist;
while (!pq_.empty()) {
top_v = pq_.top().v;
pq_.pop();
if (collected_[top_v]) continue;
collected_[top_v] = true;
if (top_v == des) {
while (!pq_.empty()) pq_.pop();
break;
}
if (dist_[top_v] * q > v_height[top_v]) continue;
for (auto it = graph[top_v].begin(); it != graph[top_v].end(); it++) {
adj_v = it->adj_v;
if (!collected_[adj_v]) {
tmp_dist = dist_[top_v] + it->adj_weight;
if (tmp_dist < dist_[adj_v] || dist_[adj_v] == NO_VALUE) {
dist_[adj_v] = tmp_dist;
pq_.push(PriorityNode(adj_v, tmp_dist));
}
}
} //for
} //while
bool result = collected_[des];
*p_shortest_dist = dist_[des];
free(dist_);
free(collected_);
return result;
}
int main() {
int n, m, s, t, g, q;
scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &g, &q);
s--; t--;
LL * height = new LL[n];
LL hi, li;
for (size_t i = 0; i < n; i++) {
scanf("%d %d", &hi, &li);
height[i] = li - hi;
}
vector<AdjNode> * graph = new vector<AdjNode>[n];
int u, v, wi;
for (size_t i = 0; i < m; i++) {
scanf("%d %d %d", &u, &v, &wi);
u--; v--;
graph[u].push_back(AdjNode(v, wi));
graph[v].push_back(AdjNode(u, wi));
}
Dijkstra dijkstra;
LL shortest_dist;
if (dijkstra.dijkstra(graph, n, s, t, q, height, &shortest_dist) && shortest_dist <= g) {
printf("%lld", shortest_dist);
}
else printf("wtnap wa kotori no oyatsu desu!");
free(height);
for (size_t i = 0; i < n; i++) {
vector<AdjNode>().swap(graph[i]);
}
return 0;
}