题意就不再赘述了
黑书上308页例1是极其相似的题。。。。
思路也一样
枚举每个点作为吃饭的地点。
每次以枚举的这个点为起点做最短路，途中不能走比它贵的点。
每次求出最短路后要更新我们的查询答案。更新其实也就是一行的样子。
假设查询的两个点有个最优的方案，那么路径上有某点是吃饭的地点，那么从该点出发按刚才的方法一定能找到查询的那两个点。
据称本题卡常数，我最后用了3400ms 的样子。
那么尽量不要用stl的东西了。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1005
#define MAXM 40005
#define INF 10000000000007LL
using namespace std;
struct EDGE
{int v, next, w;
}edge[MAXM];
int head[MAXN], e;
void init()
{memset(head, -1, sizeof(head));e = 0;
}
void add(int x, int y, int w)
{edge[e].v = y;edge[e].w = w;edge[e].next = head[x];head[x] = e++;
}
long long d[MAXN], ans[MAXM];
int a[MAXM], b[MAXM], val[MAXN];
int que[MAXM * 5], vis[MAXN];
int q, n, m;
void spfa(int src)
{for(int i = 0; i <= n; i++) d[i] = INF, vis[i] = 0;int h = 0, t = 0;vis[src] = 1;d[src] = 0;que[t++] = src;while(h < t){int u = que[h++];vis[u] = 0;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(val[v] <= val[src] && d[u] + edge[i].w < d[v]){d[v] = d[u] + edge[i].w;if(!vis[v]){vis[v] = 1;que[t++] = v;}}}}for(int i = 1; i <= q; i++)if(d[a[i]] != INF && d[b[i]] != INF && ans[i] > d[a[i]] + d[b[i]] + val[src])ans[i] = d[a[i]] + d[b[i]] + val[src];
}
int main()
{while(scanf("%d%d", &n, &m) != EOF){if(!n && !m) break;init();int u, v, w;for(int i = 1; i <= n; i++) scanf("%d", &val[i]);for(int i = 1; i <= m; i++){scanf("%d%d%d", &u, &v, &w);add(u, v, w), add(v, u, w);}scanf("%d", &q);for(int i = 1; i <= q; i++){scanf("%d%d", &a[i], &b[i]);ans[i] = INF;}for(int i = 1; i <= n; i++) spfa(i);for(int i = 1; i <= q; i++){if(ans[i] == INF) printf("-1\n");else printf("%lld\n", ans[i]);}puts("");}return 0;
}