Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has n junctions, some of which are connected by two-way roads. The length of each road is defined by some positive integer number of meters; the roads can have different lengths.
Initially each junction has exactly one taxi standing there. The taxi driver from the i-th junction agrees to drive Petya (perhaps through several intermediate junctions) to some other junction if the travel distance is not more than ti meters. Also, the cost of the ride doesn't depend on the distance and is equal to ci bourles. Taxis can't stop in the middle of a road. Each taxi can be used no more than once. Petya can catch taxi only in the junction, where it stands initially.
At the moment Petya is located on the junction x and the volleyball stadium is on the junction y. Determine the minimum amount of money Petya will need to drive to the stadium.
The first line contains two integers n and m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000). They are the number of junctions and roads in the city correspondingly. The junctions are numbered from 1 to n, inclusive. The next line contains two integers x and y (1 ≤ x, y ≤ n). They are the numbers of the initial and final junctions correspondingly. Next m lines contain the roads' description. Each road is described by a group of three integers ui, vi, wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 109) — they are the numbers of the junctions connected by the road and the length of the road, correspondingly. The next n lines contain n pairs of integers ti and ci (1 ≤ ti, ci ≤ 109), which describe the taxi driver that waits at the i-th junction — the maximum distance he can drive and the drive's cost. The road can't connect the junction with itself, but between a pair of junctions there can be more than one road. All consecutive numbers in each line are separated by exactly one space character.
If taxis can't drive Petya to the destination point, print "-1" (without the quotes). Otherwise, print the drive's minimum cost.
Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.
题目大意：给n个点，m条双向边，每条路均有一个距离，从一个点x出发，最多能花费c[x]走距离t[x]的路，求从起点到终点的最小花费。
官方题解1：
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; typedef long long LL; const int MAXN = ;
const int MAXM = ;
int n, m, x, y; void tle() {
while() ;
} struct Shortest_path {
int head[MAXN], inque[MAXN];
int next[MAXM], to[MAXM], cost[MAXM];
int ecnt, st, ed;
LL dis[MAXN]; void SPFA() {
queue<int> Q;
Q.push(st);
memset(inque, , sizeof(inque));
memset(dis, , sizeof(dis));
dis[st] = ;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inque[u] = false;
for(int p = head[u]; p; p = next[p]) {
int v = to[p];
if(dis[v] < || dis[v] > dis[u] + cost[p]) {
dis[v] = dis[u] + cost[p];
//printf("%d %I64d\n",v,dis[v]);
if(!inque[v]) {
inque[v] = true;
Q.push(v);
}
}
}
}
} void addEdge(int u, int v, int c) {
to[ecnt] = v; cost[ecnt] = c;
next[ecnt] = head[u]; head[u] = ecnt++;
//printf("%d->%d %d\n",u,v,c);
//if(ecnt == MAXM) tle();
} void init(int ss, int tt) {
st = ss; ed = tt;
ecnt = ;
memset(head, , sizeof(head));
} LL solve() {
SPFA();
return dis[ed];
}
} G; const int M = MAXN * ; struct Tree {
int head[MAXN], c[MAXN], t[MAXN];
int small[MAXN];
int next[M], to[M], cost[M];
int ecnt; void dfs(int root, int u, int rest) {
for(int p = head[u]; p; p = next[p]) {
int v = to[p];
if(rest - cost[p] < small[v]) continue;
if(rest - cost[p] >= ) {
G.addEdge(root, v, c[root]);
small[v] = rest - cost[p];
if(rest) dfs(root, v, rest - cost[p]);
}
}
} void addEdge(int u, int v, int cc) {
to[ecnt] = v; cost[ecnt] = cc;
next[ecnt] = head[u]; head[u] = ecnt++;
//printf("%d->%d %d\n",u,v,cc);
} void init() {
ecnt = ;
memset(head, , sizeof(head));
} void make_G() {
for(int i = ; i <= n; ++i) {
memset(small, , sizeof(small));
small[i] = 0x7fffffff;
dfs(i, i, t[i]);
}
}
} T; int main() {
while(scanf("%d%d", &n, &m) != EOF) {
scanf("%d%d", &x, &y);
G.init(x, y);
T.init();
int u, v, c;
for(int i = ; i < m; ++i) {
scanf("%d%d", &u, &v);
scanf("%d", &c);
T.addEdge(u, v, c);
T.addEdge(v, u, c);
}
for(int i = ; i <= n; ++i) {
scanf("%d", &T.t[i]);
scanf("%d", &T.c[i]);
}
T.make_G();
printf("%I64d\n", G.solve());
}
}
献上真·AC代码，这个应该没问题了，理论上来说上面的那个代码可以卡（可以卡边数卡爆），实际上可以直接用SPFA求第一张图的最短路然后再判断某点x是否能到底某点y，SPFA在稀疏图上常数灰常小，在这提上是灰常适用的。
PS：下面的两个类实际上可以合在一起，但是我懒得搞了就这样吧……
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; typedef long long LL; const int MAXN = ;
const int MAXM = ;
int n, m, x, y; void tle() {
while() ;
} struct Shortest_path {
int head[MAXN], inque[MAXN];
int next[MAXM], to[MAXM], cost[MAXM];
int ecnt, st, ed;
LL dis[MAXN]; void SPFA() {
queue<int> Q;
Q.push(st);
memset(inque, , sizeof(inque));
memset(dis, , sizeof(dis));
dis[st] = ;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inque[u] = false;
for(int p = head[u]; p; p = next[p]) {
int v = to[p];
if(dis[v] < || dis[v] > dis[u] + cost[p]) {
dis[v] = dis[u] + cost[p];
//printf("%d %I64d\n",v,dis[v]);
if(!inque[v]) {
inque[v] = true;
Q.push(v);
}
}
}
}
} void addEdge(int u, int v, int c) {
to[ecnt] = v; cost[ecnt] = c;
next[ecnt] = head[u]; head[u] = ecnt++;
//printf("%d->%d %d\n",u,v,c);
//if(ecnt == MAXM) tle();
} void init(int ss, int tt) {
st = ss; ed = tt;
ecnt = ;
memset(head, , sizeof(head));
} LL solve() {
SPFA();
return dis[ed];
}
} G; const int M = MAXN * ; struct Tree {
int head[MAXN], inque[MAXN], c[MAXN], t[MAXN];
int next[M], to[M], cost[M];
int ecnt;
LL dis[MAXN]; void SPFA(int st) {
queue<int> Q;
Q.push(st);
memset(inque, , sizeof(inque));
memset(dis, , sizeof(dis));
dis[st] = ;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inque[u] = false;
for(int p = head[u]; p; p = next[p]) {
int v = to[p];
if(dis[v] < || dis[v] > dis[u] + cost[p]) {
dis[v] = dis[u] + cost[p];
//printf("%d %I64d\n",v,dis[v]);
if(!inque[v]) {
inque[v] = true;
Q.push(v);
}
}
}
}
} void addEdge(int u, int v, int cc) {
to[ecnt] = v; cost[ecnt] = cc;
next[ecnt] = head[u]; head[u] = ecnt++;
//printf("%d->%d %d\n",u,v,cc);
} void init() {
ecnt = ;
memset(head, , sizeof(head));
} void make_G() {
for(int i = ; i <= n; ++i) {
SPFA(i);
for(int j = ; j <= n; ++j) {
if(i == j) continue;
if(dis[j] >= && dis[j] <= t[i]) {
G.addEdge(i, j, c[i]);
}
}
}
}
} T; int main() {
int i;
while(scanf("%d%d", &n, &m) != EOF) {
scanf("%d%d", &x, &y);
G.init(x, y);
T.init();
int u, v, c;
for(i = ; i < m; ++i) {
scanf("%d%d", &u, &v);
scanf("%d", &c);
T.addEdge(u, v, c);
T.addEdge(v, u, c);
}
for(i = ; i <= n; ++i) {
scanf("%d", &T.t[i]);
scanf("%d", &T.c[i]);
}
T.make_G();
printf("%I64d\n", G.solve());
}
}