传送门：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2352
题目大意：
n个城市有m条道路。每个城市的油价不一样，给出起点s和终点t，以及汽车的油箱的容量，求从城市s到城市 t 的最便宜路径。（一开始油箱是空的，你每次可以选择加多少升。假设每单位的距离消耗1L汽油）
思路：
dijkstra的变形。
用优先队列来维护当前花费的最小值。设dp[i][j]为到达城市i的消耗剩余汽油为j升的最小花费。
那么，经过每一站时候，如果到下一站加油可能最优，那么就加。（详见代码）
PS:
其实这个dp算状态转移吧，嗯，也算。不过我怎么觉得更像剪枝- -|||一开始没有TLE了
还有就是路是双向的。。WA了后发现。改了RE了。好吧数组太小。改了就AC了
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1000+10;
const int MAXM=30000+10;
const int INF=100000+10;
int head[MAXN],len,dis[MAXN],cost[MAXN],n,m;
int dp[MAXN][111]; //设dp[i][j]为到达城市i的消耗剩余汽油为j升的最小花费
struct edge
{
int to,val,next;
}e[MAXM];
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
struct state
{
int id,cost,move;
state(int tid,int tcanmove,int tcurcost){id=tid;cost=tcurcost;move=tcanmove;}
bool operator <(const state & x)const {
return cost > x.cost;
}
};
void dijkstra(int contain,int from,int to)
{
memset(dis,0,sizeof(dis));
for(int i=0;i<n;i++)
for(int j=0;j<101;j++)
dp[i][j]=INF;
priority_queue<state> q;
q.push(state(from,0,0));
while(!q.empty())
{
state cur=q.top();
if(cur.id==to)
{
printf("%d\n",cur.cost);
return;
}
q.pop();
if(cur.move<contain && dp[cur.id][cur.move+1] > cost[cur.id]+cur.cost) //满了不加，加了比之前的状态花费多不加
{
dp[cur.id][cur.move+1] = cost[cur.id]+cur.cost;
q.push(state(cur.id,cur.move+1,cost[cur.id]+cur.cost));
}
for(int i=head[cur.id];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(cur.move < e[i].val) continue;//不够到下一站
if(dp[e[i].to][cur.move-e[i].val] > cur.cost) // 到下一站的花费比记录的少就走起~
{
dp[e[i].to][cur.move-e[i].val] = cur.cost;
q.push(state(e[i].to,cur.move-e[i].val,cur.cost));
}
}
}
printf("impossible\n");
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(head,-1,sizeof(head));
len=0;
for(int i=0;i<n;i++)
scanf("%d",&cost[i]);
for(int i=0;i<m;i++)
{
int from,to,val;
scanf("%d%d%d",&from,&to,&val);
add(from,to,val);
add(to,from,val);
}
int q;
scanf("%d",&q);
while(q--)
{
int c,s,e;
scanf("%d%d%d",&c,&s,&e);
dijkstra(c,s,e);
}
}
return 0;
}