P – FULL TANK?

題目大意：

給定一張圖，和每個(gè)點(diǎn)的油價(jià)，知道每條路的耗油量，給定一些詢(xún)問(wèn)，求從起點(diǎn)到終點(diǎn)用指定油箱容量的車(chē)所得到的最小耗費(fèi)。

解題思路：

BFS+優(yōu)先隊(duì)列

優(yōu)先隊(duì)列介紹：采用stl中的priority_queue實(shí)現(xiàn)。priority_queue默認(rèn)的是最大優(yōu)先隊(duì)列，聲明時(shí)只要priority_queue<int> q就行了。如果是最小堆，麻煩一些

priority_queue<int,vector<int>,cmp> q。其中cmp函數(shù)如下：
struct cmp
{
    bool operator()(const int &i,const int &j)
    {
        return i>j;//注意：是“>”而不是“<”。
    }
}

圖存儲(chǔ)：本題采用鄰接表的形式存儲(chǔ)圖。采用stl中的vector實(shí)現(xiàn)。首先定義數(shù)據(jù)結(jié)構(gòu)如下： 

typedef struct
{
    int e;//鄰接點(diǎn)
    int dist;//距離
}edge;

然后定義vector數(shù)組： 

vector<edge> graph[N];//N為頂點(diǎn)數(shù)

vector實(shí)現(xiàn)鄰接表比普通二維數(shù)組實(shí)現(xiàn)更優(yōu)的地方在于它不用記錄各個(gè)點(diǎn)鄰接點(diǎn)的個(gè)數(shù)，而只用一個(gè)簡(jiǎn)單的push_back()函數(shù)就輕松實(shí)現(xiàn)了邊的記錄。

題目解答：

1.到i城市所花的費(fèi)用作為優(yōu)先隊(duì)列的權(quán)值。

2.定義如下結(jié)構(gòu)體記錄當(dāng)前狀態(tài)： 

typedef struct
{
    int p;//當(dāng)前城市
    int q;//油箱中剩余的油
    int sp;//當(dāng)前花費(fèi)
}state;

3.定義標(biāo)記數(shù)組isvis[N][M]記錄到城市p還剩q升油這個(gè)狀態(tài)。

4.初始化將開(kāi)始狀態(tài)(u,0,0)加入隊(duì)列。

5.然后每次取優(yōu)先隊(duì)列隊(duì)頭元素對(duì)隊(duì)頭中的城市進(jìn)行擴(kuò)展（出隊(duì)列的時(shí)候?qū)svis[p][q]進(jìn)行標(biāo)記）?？梢赃x擇加油或者不加油。加油的話每次加一升（如果加一升不超過(guò)油箱容量），然后相應(yīng)的狀態(tài)也進(jìn)行改變（u,+1,+p）[其中p為當(dāng)前城市的油價(jià)]，如果當(dāng)前狀態(tài)能到下一個(gè)城市，則下一個(gè)城市的狀態(tài)也入隊(duì)列。然后循環(huán)執(zhí)行5。直到出隊(duì)列的城市是目的城市為止。

注意：

1.因?yàn)殛?duì)列是按花費(fèi)為權(quán)值的，所以當(dāng)一種狀態(tài)已經(jīng)被標(biāo)記為真的時(shí)候，說(shuō)明出來(lái)的花費(fèi)已經(jīng)是最小的了。所以隊(duì)列后面出來(lái)的相同狀態(tài)可以直接跳過(guò)，不做處理。

2.對(duì)當(dāng)前城市進(jìn)行擴(kuò)展的時(shí)候，可能有擴(kuò)展后的狀態(tài)已經(jīng)出隊(duì)列了。這說(shuō)明這個(gè)擴(kuò)展后的狀態(tài)比當(dāng)前狀態(tài)已經(jīng)有了一個(gè)更優(yōu)的解（優(yōu)先隊(duì)列的結(jié)果），而當(dāng)前狀態(tài)擴(kuò)展的狀態(tài)花費(fèi)肯定比當(dāng)前的多（因?yàn)閿U(kuò)展的時(shí)候加油，加油花錢(qián)）。所以，這個(gè)狀態(tài)就不需要再進(jìn)隊(duì)列了。這是兩個(gè)利用了優(yōu)先隊(duì)列性質(zhì)進(jìn)行的剪枝。

核心代碼： 

void bfs(){
	int i,j,k,w;
	priority_queue<state,vector<state>,cmp> que;
	for(i=0;i<n;i++)
	{
		for(j=0;j<101;j++)
		{
			us[i][j]=MAX;//初始為無(wú)窮大
			isvis[i][j]=false;
		}
	}
	state s;
	s.p=u;
	s.q=0;
	s.sp=0;
	us[u][0]=0;
	que.push(s);
//	isvis[s.p][s.q]=true;
	state cur,tmp;
	while(!que.empty()){
		cur=que.top();
		que.pop();
		if(isvis[cur.p][cur.q]==true)
			continue;
		isvis[cur.p][cur.q]=true;
		if(cur.p==v)
		{
			res=cur.sp;
			return;
		}
		if(cur.q+1<=c&&isvis[cur.p][cur.q+1]==false)//當(dāng)前加一升油之后不超過(guò)油箱容量
		{
			us[cur.p][cur.q+1]=us[cur.p][cur.q]+p[cur.p];
			tmp.p=cur.p;
			tmp.q=cur.q+1;
			tmp.sp=us[cur.p][cur.q+1];
			que.push(tmp);
		}
		for(i=0;i<graph[cur.p].size();i++)
		{
			w=graph[cur.p][i].e;
			k=cur.q-graph[cur.p][i].dis;//從p城市到i城市還剩下的油
			if(k>=0&&isvis[w][k]==false&&cur.sp<us[w][k])//當(dāng)前的消費(fèi)小于到城市w用油k升的最小費(fèi)用
			{
				us[w][k]=cur.sp;
				tmp.p=w;
				tmp.q=k;
				tmp.sp=cur.sp;
				que.push(tmp);
//				isvis[tmp.p][tmp.q]=true;
			}
		}
	}
}