POJ 4046 Sightseeing 最短路

题意就不再赘述了

黑书上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;
}