【题目】点击打开链接，密码acm2016

【题意】n个点m条边的有向图，q次询问c，s，t，表示汽车邮箱容量为c，求从起点s到终点t的最小费用。汽车在每个点可以加任意的油，每个点的油价为a[i]。

【题目分析】优先队列的Dij，每个节点保存还剩下的油量fuel和到当前为止所用的花费，dis[i][j]表示在i点油量还剩下j的费用最小值。注意，每次入队列不要一次性把所有符合的油量全部入队列，比如u->v，距离为w，那么油量区间w~c之间的油量都是可以满足从u走到v的，但不要一次性把w~c全部入队列，这样会超时：应该这样：对于队列中的每个点u先看它当前的油量能否顺着边走到下一个节点v去更新v，如果可以就更新v，然后当前点u的油量还可以增加就把它的油量增加一再入队列。

【补充】还有一种记录三维的状态，dp[i][j][k]，分别表示费用，剩余油量，所在城市。最小费用优先。但这里没有必要记录在哪个城市，因为维护是最小值。

【AC代码】

#include <stdio.h>
#include <queue>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 102;
const int maxm = 1002;
struct Edge{
   int u,v,w,next;
}E[maxm];
struct node{
   int id,fuel,cost;
   node(){};
   node(int a,int b,int c):id(a),fuel(b),cost(c){};
   friend bool operator<(const node &x,const node &y)
   {
      return x.cost>y.cost;
   }
};

int n,m,cap,s,e;
int num,head[maxn],dis[maxn][maxn];
int a[maxn];//在某个点加油的花费
void init()
{
    num=0;
    memset(head,-1,sizeof(head));
}
void Add_Edge(int u,int v,int w)
{
    E[num].u=u;
    E[num].v=v;
    E[num].w=w;
    E[num].next=head[u];
    head[u]=num++;
}
void Dijstra(int cap,int s,int e);
int main()
{
    int T,cas=1;
    int u,v,w,q;
//    int cap,s,e;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++)scanf("%d",&a[i]);
        init();
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            Add_Edge(u,v,w);
            Add_Edge(v,u,w);
        }
//        Dijstra();
        scanf("%d",&q);
        printf("Case %d:\n",cas++);
        while(q--)
        {
            scanf("%d%d%d",&cap,&s,&e);
            Dijstra(cap,s,e);
        }
    }
    return 0;
}

void Dijstra(int cap,int s,int e)
{
    int u,v;
    node cur;
    memset(dis,INF,sizeof(dis));
    priority_queue<node>que;
    dis[s][0]=0;
    que.push(node(s,0,0));
    while(!que.empty())
    {
        cur=que.top();
        que.pop();
        u=cur.id;
        if(dis[u][cur.fuel]<cur.cost)continue;//在当前点的费用最小值比当前点的花费还要小，就不需要优化
        for(int i=head[u]; ~i; i=E[i].next)
        {
            v = E[i].v;
            if(cur.fuel>=E[i].w&&dis[v][cur.fuel-E[i].w]>dis[u][cur.fuel])
            {
                dis[v][cur.fuel-E[i].w] = dis[u][cur.fuel];
                que.push(node(v,cur.fuel-E[i].w,dis[u][cur.fuel]));
            }
        }
        if(cur.fuel<cap&&dis[u][cur.fuel+1]>dis[u][cur.fuel]+a[u])
        {
            dis[u][cur.fuel+1]=dis[u][cur.fuel]+a[u];
            que.push(node(u,cur.fuel+1,dis[u][cur.fuel]+a[u]));
        }
    }
    int ans=INF;
    for(int i=0; i<=cap; i++)ans=min(dis[e][i],ans);
    if(ans==INF)puts("impossible");
    else
    printf("%d\n",ans);
}