題意：
? ? ?給你一個(gè)有向圖，然后求從起點(diǎn)到終點(diǎn)的最短，但是還有一個(gè)限制，就是總花費(fèi)不能超過(guò)k，也就是說(shuō)每條邊上有兩個(gè)權(quán)值，一個(gè)是長(zhǎng)度，一個(gè)是花費(fèi)，求滿足花費(fèi)的最短長(zhǎng)度。


思路：
? ? ? 一開(kāi)始寫了一個(gè)mark[i][j]第i個(gè)點(diǎn)花費(fèi)j狀態(tài)的spfa，TLE了，然后又優(yōu)化了下，就是先反向搜索一遍簡(jiǎn)單最短路（以花費(fèi)為權(quán)值）然后用這個(gè)結(jié)果在mark[][]二維的最短路里面剪枝用，結(jié)果還是超時(shí)了，然后又嘗試了下優(yōu)先隊(duì)列，結(jié)果900+ac險(xiǎn)過(guò)，我把自己的第一個(gè)優(yōu)化去掉，結(jié)果跑了800+,哎！對(duì)于在spfa上使用優(yōu)先隊(duì)列，這個(gè)我感覺(jué)還是不是很靠譜啊，如果不考慮優(yōu)先隊(duì)列的時(shí)間復(fù)雜度跑spfa確實(shí)是個(gè)優(yōu)化，因?yàn)楫吘褂悬c(diǎn)貪心的意思（具體能優(yōu)化多少，要看數(shù)據(jù)，總之不會(huì)像記憶化搜索那樣級(jí)別的優(yōu)化就是了），可是優(yōu)先隊(duì)列的操作時(shí)間是log級(jí)別的，在他們兩個(gè)之間去衡量，還是要看具體數(shù)據(jù)啊。


這是個(gè)有反向搜索預(yù)處理優(yōu)化的ac代碼，把反向預(yù)處理去掉之后會(huì)更快一點(diǎn)（哎！）


#include<queue>
#include<stdio.h>
#include<string.h>


#define N_node 100 + 5
#define N_edge 10000 + 10
#define INF 100000000


using namespace std;


typedef struct
{
? ? int to ,next ,cost ,time;
}STAR;


typedef struct
{
? ? int to ,next ,cost;
}STAR2;


typedef struct NODE
{
? ? int id ,cost ,time;
? ? friend bool operator < (NODE a ,NODE b)
? ? {
? ? ? ? return a.cost > b.cost || a.cost == b.cost && a.time > b.time;
? ? }
}NODE;


int list[N_node] ,tot;
int list2[N_node] ,tot2;
int mark[N_node][10000+5];
int ?s_x[N_node][10000+5];
int s_x2[N_node];
STAR E[N_edge];
STAR2 E2[N_edge];
NODE xin ,tou;


void add(int a ,int b ,int c ,int d)
{
? ? E[++tot].to = b;
? ? E[tot].cost = c;
? ? E[tot].time = d;
? ? E[tot].next = list[a];
? ? list[a] = tot;
}


void add2(int a ,int b ,int c)
{
? ? E2[++tot2].to = b;
? ? E2[tot2].cost = c;
? ? E2[tot2].next = list2[a];
? ? list2[a] = tot2;
}






void Spfa(int s ,int n ,int maxtime)
{
? ? for(int i = 0 ;i <= n ;i ++)
? ? for(int j = 0 ;j <= maxtime ;j ++)
? ? s_x[i][j] = INF ,mark[i][j] = 0;
? ? priority_queue<NODE>q;
? ? xin.id = 1 ,xin.cost = xin.time = 0;
? ? q.push(xin);
? ? s_x[xin.id][xin.time] = 0;
? ? mark[xin.id][xin.time] = 1;
? ? while(!q.empty())
? ? {
? ? ? ? tou = q.top();
? ? ? ? q.pop();
? ? ? ? mark[tou.id][tou.time] = 0;
? ? ? ? for(int k = list[tou.id] ;k ;k = E[k].next)
? ? ? ? {
? ? ? ? ? ? xin.id = E[k].to;
? ? ? ? ? ? xin.cost = tou.cost + E[k].cost;
? ? ? ? ? ? xin.time = tou.time + E[k].time;
? ? ? ? ? ? if(xin.time + s_x2[xin.id]> maxtime) continue;
? ? ? ? ? ? if(s_x[xin.id][xin.time] > s_x[tou.id][tou.time] + E[k].cost)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s_x[xin.id][xin.time] = s_x[tou.id][tou.time] + E[k].cost;
? ? ? ? ? ? ? ? if(!mark[xin.id][xin.time])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mark[xin.id][xin.time] = 1;
? ? ? ? ? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }


? ? ? ? }
? ? }
}


void Spfa2(int s ,int n)
{
? ? int mk[N_node] = {0};
? ? for(int i = 0 ;i <= n ;i ++)
? ? s_x2[i] = INF;
? ? queue<int>q;
? ? q.push(s);
? ? mk[s] = 1;
? ? s_x2[s] = 0;
? ? while(!q.empty())
? ? {
? ? ? ? int xin ,tou;
? ? ? ? tou = q.front();
? ? ? ? q.pop();
? ? ? ? mk[tou] = 0;
? ? ? ? for(int k = list2[tou] ;k ;k = E2[k].next)
? ? ? ? {
? ? ? ? ? ? xin = E2[k].to;
? ? ? ? ? ? if(s_x2[xin] > s_x2[tou] + E2[k].cost)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s_x2[xin] = s_x2[tou] + E2[k].cost;
? ? ? ? ? ? ? ? if(!mk[xin])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mk[xin] = 1;
? ? ? ? ? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
}






int main ()
{
? ? int n ,m ,maxtime ,i;
? ? int a ,b ,c ,d;
? ? while(~scanf("%d" ,&maxtime))
? ? {
? ? ? ? scanf("%d %d" ,&n ,&m);
? ? ? ? memset(list ,0 ,sizeof(list));
? ? ? ? memset(list2 ,0 ,sizeof(list2));
? ? ? ? tot = 1 ,tot2 = 1;
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);
? ? ? ? ? ? add(a ,b ,c ,d);
? ? ? ? ? ? add2(b ,a ,d);
? ? ? ? }
? ? ? ? Spfa2(n ,n);
? ? ? ? Spfa(1 ,n ,maxtime);
? ? ? ? int ans = INF;
? ? ? ? for(i = 1 ;i <= maxtime ;i ++)
? ? ? ? if(ans > s_x[n][i]) ans = s_x[n][i];
? ? ? ? if(ans == INF) ans = -1;
? ? ? ? printf("%d\n" ,ans);
? ? }
? ? return 0;
}









《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的POJ1722二维spfa+优先队列优化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。