UVA 11367満タン油解題報告

【問題の説明】
 
n都市間のm本の道路を与える.始点Aと終点B、および自動車のメールボックス容量cを与え、AからBまでの最も安い経路を計算する.初期のメールボックスが空であると仮定します.i番目の都市の原油価格はpiです.Qグループの問い合わせに答える必要があります. 
 
【入力形式】
 
第1の挙動n,mは、都市数と道路数を表し、そのうち都市番号は1である.n.次のn行は、各行に1つの整数pi、i+1行目のpiは、i番目の都市の原油価格がpiであることを示す.さらに次のm+1行は、行ごとに1つの道路a,b,d(0<=a,b
 
【出力形式】
 
質問ごとに1つの整数を出力、質問に対応する最も安いパスを表し、到着できない場合はimpossibleを出力する.
 
【入力サンプル】
 
5 5
10
10
20
12
13
1 2 9
1 3 8
2 3 1
2 4 11
3 4 7
2
10 2 4
20 3 5 
 
【出力サンプル】
 
80
impossible
 
【データ範囲】
 
n<=200  m<=10000  q<=100  0  
【出所】
 
『大白書』UVa 11367
UVa問題ライブラリのこの問題の都市は0からn-1番の都市であり、n<=1000であることに注意してください.
解題の構想はコードとコードの中の解釈を見て、以下のコードはUVaの原題を通過するコードです.

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1005;
const int inf=1000000010;
int N,M,a,b,q,c;
int p[maxn];
vectorg[maxn],w[maxn];
struct data
{
	int id,v,s;
	friend bool operator < (data aa,data bb)
	{
		return aa.v>bb.v;
	}
};
int d[maxn][105];  //f(i,j)    i     j         
void DIJ(int s)
{
	priority_queueq;
	for(int i=0;i<=N;i++)
	for(int j=0;j<=c;j++)
	d[i][j]=inf;
	q.push((data){s,0,0});
	d[s][0]=0;
	while(!q.empty())
	{
		data t=q.top();  q.pop();
		int i=t.id;
		if(i==b)   //                 ，       ，         ，          
		{
			printf("%d
",t.v);
			return;
		}
		if(d[i][t.s]t.v+p[i])  //    ，           ，      
		{
			d[i][t.s+1]=t.v+p[i];
			q.push((data){i,d[i][t.s+1],t.s+1});
		}
		for(int k=0;k