小生成樹并查集最短路-資料下載頁
2025-05-13 11:21本頁面
【正文】 根據(jù)上面的思想一步步來實現(xiàn)： ? const int M=105。 ? const int oo=100000000。 ? struct node { int to,next,cap。 ? } edge[M*100]。 ? int head[2*M], Q[M*M], mark[2*M]。 ? int cost[2*M]。 ? int n,e,src,tot。 最短路徑 SPFA ? void add(int a, int b, int c) { edge[tot].to=b, edge[tot].cap=c, edge[tot].next=head[a], head[a]=tot++。 ? } //臨界表，添加邊 最短路徑 SPFA ? SPFA函數(shù)前半部分 ? void spfa(){ for(int i=1。 i=n。 i++) { cost[i]=oo。 mark[i]=0。 } cost[src]=0。 mark[src]=1。 int l=0,h=0,k,y。 Q[l++]=src。 最短路徑 SPFA ? SPFA后半部分 ? while(hl){ ? k=Q[h++]。 ? mark[k]=0。 ? for(int i=head[k]。 i!=1。 i=edge[i].next) { ? y=edge[i].to。 ? if (cost[y]cost[k]+edge[i].cap) { ? cost[y]=cost[k]+edge[i].cap。 ? if(!mark[y]){ //避免重復入列 ? Q[l++]=y。 ? mark[y]=1。 ? } ? } ? } ? } ? } 最短路徑 SPFA ? 主函數(shù) ? int main(){ ? while(scanf(%d%d,amp。n,amp。e) != EOF){ ? if(n==0 amp。amp。 e==0) break。 ? tot=0。 ? for(int i=1。 i=n。 i++) head[i]=1。 ? for(int i=1。 i=e。 i++){ ? int u,w,v。 ? scanf(%d%d%d,amp。u,amp。w,amp。v)。 ? add(u,w,v)。 add(w,u,v)。 ? } ? int st=1,ed=n。 ? src=st。 ? spfa()。 ? printf(%d\n,cost[ed])。 ? } ? } 最短路徑 SPFA ? 需要注意的地方： 是雙向邊 主函數(shù)里對臨界表的初始化 SPFA函數(shù)里的標記數(shù)組 mark 隊列的使用，空間大小 最短路徑 SPFA ? 其他相關(guān)練習： ? HDU 3790 ? PKU 1151 ? PKU 2387 最短路的算法有很多， SPFA是很高效的一種，但希望大家對一般算法也去了解下，對比中發(fā)現(xiàn)優(yōu)劣 大家休息了，下課 ~ Thank You ~
研究報告相關(guān)推薦
鄂ICP備17016276號-1