View Code of Problem 1067

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxm 10010
#define maxn 1010

using namespace std;

struct Edge
{
    int to,val,next;
}edge[maxm*2];

struct node
{
    int id,cost,oil;
    bool operator <(const node &b) const
    {
        return cost > b.cost;
    }
};
bool vis[maxn][110];
int cnt,head[maxn],dp[maxn][110],ans,st,ed,cap,p[maxn];
priority_queue<node> q;

void add(int x,int y,int z)
{
    edge[cnt].to = y;
    edge[cnt].val = z;
    edge[cnt].next = head[x];
    head[x] = cnt++;
}

bool bfs()
{
    memset(dp,0x3f,sizeof(dp));
    memset(vis,0,sizeof(vis));
    while(!q.empty())
        q.pop();
    int id,oil,cost;
    ans = 0;

    dp[st][0] = 0;
    node now,cur,next;
    now.id = st;
    now.cost = 0;
    now.oil = 0;
    q.push(now);
    while(!q.empty())
    {
        cur = q.top();
        q.pop();
        id = cur.id,oil = cur.oil,cost = cur.cost;
        if(id == ed)
        {
            ans = cost;
            return true;
        }
        if(vis[id][oil]) continue;
        vis[id][oil] = true;
        if(oil < cap)
        {
            next.id = id;
            next.cost = cost+p[id];
            next.oil = oil+1;
            if(dp[next.id][next.oil]>next.cost && !vis[next.id][next.oil])
            {
                dp[next.id][next.oil] = next.cost;
                q.push(next);
            }
        }
        for(int i=head[id];i!=-1;i = edge[i].next)
        {
            int u = edge[i].to;
            int w = edge[i].val;
            if(oil>=w && dp[u][oil-w]>cur.cost && !vis[u][oil-w])
            {
                next.oil = oil-w;
                next.id = u;
                next.cost = cost;
                dp[u][next.oil] = next.cost;
                q.push(next);
            }
        }
    }
    return false;
}

int main()
{
    int n,m,u,v,l,que;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        cnt = 0;

        for(int i=0;i<n;i++)
            scanf("%d",&p[i]);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&l);
            add(u,v,l);
            add(v,u,l);
        }
        scanf("%d",&que);
        while(que--)
        {
            scanf("%d%d%d",&cap,&st,&ed);
            if(bfs())
                printf("%d\n",ans);
            else printf("impossible\n");
        }
    }
    return 0;
}