学步园

        题意：现有N个点(n<=1000)，m条边(m<=10000)，在每个点都可以加油，告诉你每个点加油的单价，现在有一些询问，每个询问有油箱大小，始点，终点。输出每个询问的最小费用，不可能输出impossible.

        注意：使用优先队列（排序也是一样，反正用到堆的）时，注意你比较的值插入队列后就不要改变，因为如果改变了，但它在队列中的位置仍不变，那么就会不对应，导致出错。

        分析：对于每个查询，有状态mo[i][j]在i城市还剩油j所用的最少的钱

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn=1100;
const int maxm=11000;
const int maxc=110;
const int maxint=0x3fffffff;
struct point
{
	int u,v,w,c;
}p0,p1;
vector<point> e[maxn];
int n,c,s,t,mo[maxn][maxc],a[maxn];
bool operator >(point a,point b)
{
	return a.w>b.w;//这里不能用mo[a.v][a.c]>mo[b.v][b.c],
}
priority_queue <point,vector<point>,greater<point> >p;

void S()
{
	int i,j,k;
	bool tag;
	while(!p.empty())
		p.pop();
	
	for(i=0;i<n;i++)
		for(j=0;j<=c;j++)
			mo[i][j]=maxint;

	mo[s][0]=0;
	p0.v=s;
	p0.c=0;
	p0.w=0;
	p.push(p0);
	tag=false;
	while(!p.empty())
	{
		p0=p.top();
		p.pop();
		if(p0.w!=mo[p0.v][p0.c])//费用不是最少时，说明前面已经有最少的往后更新了，所以没用了
			continue;
		j=p0.v;
		if(j==t)
		{
			tag=true;
			printf("%d\n",p0.w);
			break;
		}
		if(p0.c+1<=c&&mo[j][p0.c+1]>mo[j][p0.c]+a[j])
		{
			mo[j][p0.c+1]=mo[j][p0.c]+a[j];
			p1.v=j,p1.c=p0.c+1,p1.w=mo[j][p1.c];
			p.push(p1);
		}
		for(i=0;i<e[j].size();i++)
		{
			if(p0.c<e[j][i].w) continue;
			k=e[j][i].v;
			if(mo[k][p0.c-e[j][i].w]>mo[j][p0.c])
			{
				mo[k][p0.c-e[j][i].w]=mo[j][p0.c];
				p1.v=k,p1.c=p0.c-e[j][i].w;
				p1.w=mo[k][p1.c];
				p.push(p1);
			}
		}
	}
	if(!tag)
		printf("impossible\n");
}
int main()
{
	int m,q,i;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=0;i<n;i++)
		{
			e[i].clear();
			scanf("%d",&a[i]);
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&p0.u,&p0.v,&p0.w);
			e[p0.u].push_back(p0);
			swap(p0.u,p0.v);
			e[p0.u].push_back(p0);
		}
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d%d%d",&c,&s,&t);
			S();
		}
	}
	return 0;
}