【POJ 3635】 Full Tank

【题目链接】
【算法】
优先队列BFS
实现类似于堆优化dijkstra
【代码】
#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 1010

#define MAXM 10010

#define MAXC 110

const int INF = 2e9;

int i,n,m,q,tot,u,v,d,c,s,t,ans;

int head[MAXN];

bool visited[MAXN][MAXC];

int dist[MAXN][MAXC];

int p[MAXN];

struct info

{

        int pos,w,d;

        friend bool operator < (info a,info b)

        {

                return a.d > b.d;

        }

} ;

struct Edge

{

        int to,w,nxt;

} e[MAXM<<];

inline void add(int u,int v,int w)

{

        tot++;

        e[tot] = (Edge){v,w,head[u]};

        head[u] = tot;

}

inline int bfs(int c,int s,int t)

{

        int i,j;

        priority_queue< info > q;

        info cur;

        for (i = ; i <= n; i++)

        {

                for (j = ; j <= c; j++)

                {

                        dist[i][j] = INF;

                }

        }

        memset(visited,false,sizeof(visited));

        dist[s][] = ;

        while (!q.empty()) q.pop();

        q.push((info){s,,});

        while (!q.empty())

        {

                cur = q.top();

                q.pop();

                if (visited[cur.pos][cur.w]) continue;

                if (cur.pos == t) return dist[cur.pos][cur.w];

                visited[cur.pos][cur.w] = true;

                if (cur.w < c)

                {

                        if (dist[cur.pos][cur.w] + p[cur.pos] < dist[cur.pos][cur.w+])

                        {

                                dist[cur.pos][cur.w+] = dist[cur.pos][cur.w] + p[cur.pos];

                                q.push((info){cur.pos,cur.w+,dist[cur.pos][cur.w+]});

                        }

                }

                for (i = head[cur.pos]; i; i = e[i].nxt)

                {

                        if (cur.w >= e[i].w)

                        {

                                if (dist[cur.pos][cur.w] < dist[e[i].to][cur.w-e[i].w])

                                {

                                        dist[e[i].to][cur.w-e[i].w] = dist[cur.pos][cur.w];

                                        q.push((info){e[i].to,cur.w-e[i].w,dist[e[i].to][cur.w-e[i].w]});

                                }

                        }

                }

        }

        return -;

}

int main()

{

        scanf("%d%d",&n,&m);

        for (i = ; i < n; i++) scanf("%d",&p[i]);

        for (i = ; i <= m; i++)

        {

                scanf("%d%d%d",&u,&v,&d);

                add(u,v,d);

                add(v,u,d);

        }

        scanf("%d",&q);

        while (q--)

        {

                scanf("%d%d%d",&c,&s,&t);

                ans = bfs(c,s,t);

                if (ans == -) printf("impossible\n");

                else printf("%d\n",ans);

        }

        return ;

}