PKU 1511 SPFA 靜態鄰接表

2022-11-24 21:41:17 字數 920 閱讀 4259

/*

題意:給出一個圖,求源點到其他各個點之和 加上 其他各個點到源點之和的最小值

思路:spfa, 建兩個表,順序不說,

逆序的情況:在初始化的時候在反向儲存另一相同表

即: 1 ---> 2 13

反向後:2 ---> 1 13

要求各點到源點的距離和,即求源點到各點的距離和

所以,處理好後,只要求兩次源點到各點距離和相加即可

精髓:靜態鄰接表 !!!!

頭一次接觸這個東西,**幾乎是看著別人的寫出來的,自己也有少許優化

很給力的東西,尤其是 逆向實現連結串列的傳遞,收穫不小

*/#include using namespace std;

const int max = 1000001;

const int inf = int_max;//!!!!!!!!!!1!!!!!!!!!!

int n,m,n;

typedef struct vol

voll;

voll peo[max],rev[max];

int start1[max], start2[max];

int queue[max]; //優化序列

int path[max]; // path[i] 從1即到i當前最短路

__int64 spfa( voll peor, int startt)

path[temp] = 0;

queue[0] = temp;

while(start}

} //

__int64 sum=0;

for(i=1;i<=n;i++)

return sum;

}void init()

}int main()

return 0;

}