洛谷P2299題解:Dijkstra+堆優化

来源:https://www.cnblogs.com/Warframe-Gauss/archive/2020/07/27/13387717.html
-Advertisement-
Play Games

又是好久沒有寫題解了。。。。。 1.題意分析: P2299是一道非常經典的圖論最短路練習題。 圖論最短路是圖論中非常重要的一個知識模塊,其主要演算法有Dijkstra,Bellman-Ford,SPFA和Floyd。在這片題解中我們著重介紹Dijkstra演算法。 2.演算法詳解: Dijkstra應該是 ...


又是好久沒有寫題解了。。。。。

1.題意分析:

P2299是一道非常經典的圖論最短路練習題。

圖論最短路是圖論中非常重要的一個知識模塊,其主要演算法有Dijkstra,Bellman-Ford,SPFA和Floyd。在這片題解中我們著重介紹Dijkstra演算法。

2.演算法詳解:

Dijkstra應該是各位在學習圖論的時候耳熟能詳的一種演算法,也是Dijkstra帶我走進了圖論的大門。

Dijkstra演算法的發明者是Edsger Wybe Dijkstra,請大家記住這個人,因為他是信息學領域的一位大拿。

他的另一項成就相信也有很多大佬知道,那就是“go to有害論”。

話說回來,我們再來仔細看看Dijkstra演算法是怎樣運行和實現的。

程式的邏輯如下:

  • 維護兩個集合,一直最短路徑節點集合A和這些點向外擴散的鄰居節點集合B。

  • 把整張圖的起點s放到A中,把s中所有鄰居放到B中,這樣的話鄰居到s的距離就是直連距離。

  • 從B中找出距離起點s最短的節點u,放到A中。

  • 把節點u的所有新鄰居放到B中,註意要將$u$的所有鄰居都放進去。例如u有一個鄰居v,那麼v到s的距離dis(s,v)就是dis(s,u)+dis(u,v)

  • 重覆執行前面兩步,直到B為空時結束。

3.演算法代碼實現:

我們這裡講解的代碼是用一個優先隊列(priority queue)來實現的,這樣可以最大限度的優化時間。

先貼總代碼(也就是這道題的):

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int tot=0;
int ner[200001],edge[200001],nxt[200001],head[200001],b[200001],dis[200001];
void add(int x,int y,int z)//使用鄰接表,在這裡加入邊
{
	ner[++tot]=y;
	edge[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
}
priority_queue< pair<int,int> > q;//定義優先隊列
inline bool read(LL &num)//快速讀入,建議大家當做模板背牢
{
	char in;
	bool isn=false;
	in=getchar();
	if(in==EOF) return false;
	while(in!='-'&&(in<'0'||in>'9')) in=getchar();
	if(in=='-') {isn=true;num+=in-'0';}
	else num=in-'0';
	while(in=getchar(),in>='0'&&in<='9') {num*=10;num+=in-'0';}
	if(isn) num=-num;
	return true;
}
int main()
{
	LL n,m,i,x,y,z;
	read(n);
	read(m);
	for(i=1;i<=m;i++)
	{
		read(x);//使用快速讀入讀入起點終點和邊權
		read(y);
		read(z);
		add(x,y,z);//因為是無向圖,所以要加兩次邊
		add(y,x,z);
		if(x==1) dis[y]=z;//如果起點是x,那麼直連y
	}
	memset(dis,0x7f7f7f7f,sizeof(dis));
	memset(b,0,sizeof(b));//非常必要的初始化
	dis[1]=0;
	q.push(make_pair(0,1));
	while(q.size())//這裡的隊列q模擬的是集合B,當B為空時跳出迴圈
	{
		int c=q.top().second;//找出隊頭
		q.pop();
		if(b[c]) continue;
		b[c]=1;
		for(int j=head[c];j;j=nxt[j])//迴圈遍歷當前節點的鄰居
	    	{
	        	y=ner[j];
			z=edge[j];
			if(z<0x7f7f7f7f)
            		{
                		if(dis[y]>dis[c]+z)//更新當前鄰居到節點u的距離,在圖論中我們稱為“鬆弛”
                		{
                    			dis[y]=dis[c]+z;
                    			q.push(make_pair(-dis[y],y));
				}
            		}
        	}
	}
    	dis[1]=0;
    	printf("%d",dis[n]);//輸出最終結果
	return 0;
}

代碼的解釋已經在註釋中給出了,如果有不明白歡迎私信我!


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
一周排行
    -Advertisement-
    Play Games
  • 一:背景 1.講故事 在分析的眾多dump中,經常會遇到各種奇葩的問題,僅通過dump這種快照形式還是有很多問題搞不定,而通過 perfview 這種粒度又太粗,很難找到問題之所在,真的很頭疼,比如本篇的 短命線程 問題,參考圖如下: 我們在 t2 時刻抓取的dump對查看 短命線程 毫無幫助,我根 ...
  • 在日常後端Api開發中,我們跟前端的溝通中,通常需要協商好入參的數據類型,和參數是通過什麼方式存在於請求中的,是表單(form)、請求體(body)、地址欄參數(query)、還是說通過請求頭(header)。 當協商好後,我們的介面又需要怎麼去接收這些數據呢?很多小伙伴可能上手就是直接寫一個實體, ...
  • 許多情況下我們需要用到攝像頭獲取圖像,進而處理圖像,這篇博文介紹利用pyqt5、OpenCV實現用電腦上連接的攝像頭拍照並保存照片。為了使用和後續開發方便,這裡利用pyqt5設計了個相機界面,後面將介紹如何實現,要點包括界面設計、邏輯實現及完整代碼。 ...
  • 思路分析 註冊頁面需要對用戶提交的數據進行校驗,並且需要對用戶輸入錯誤的地方進行提示! 所有我們需要使用forms組件搭建註冊頁面! 平時我們書寫form是組件的時候是在views.py裡面書寫的, 但是為了接耦合,我們需要將forms組件都單獨寫在一個地方,需要用的時候導入就行! 例如,在項目文件 ...
  • 思路分析 登錄頁面,我們還是採用ajax的方式提交用戶數據 唯一需要學習的是如何製作圖片驗證碼! 具體的登錄頁面效果圖如下: 如何製作圖片驗證碼 推導步驟1:在img標簽的src屬性里放上驗證碼的請求路徑 補充1.img的src屬性: 1.圖片路徑 2.url 3.圖片的二進位數據 補充2:字體樣式 ...
  • 哈嘍,兄弟們! 最近有許多小伙伴都在吐槽打工好難。 每天都是執行許多重覆的任務 例如閱讀新聞、發郵件、查看天氣、打開書簽、清理文件夾等等, 使用自動化腳本,就無需手動一次又一次地完成這些任務, 非常方便啊有木有?! 而在某種程度上,Python 就是自動化的代名詞。 今天就來和大家一起學習一下, 用 ...
  • 作者:IT王小二 博客:https://itwxe.com 前面小二介紹過使用Typora+PicGo+LskyPro打造舒適寫作環境,那時候需要使用水印功能,但是小二在升級LskyPro2.x版本發現有很多不如人意的東西,遂棄用LskyPro使用MinIO結合代碼實現自己需要的圖床功能,也適合以後 ...
  • OpenAI Gym是一款用於研發和比較強化學習演算法的工具包,本文主要介紹Gym模擬環境的功能和工具包的使用方法,並詳細介紹其中的經典控制問題中的倒立擺(CartPole-v0/1)問題。最後針對倒立擺問題如何建立控制模型並採用爬山演算法優化進行了介紹,並給出了相應的完整python代碼示例和解釋。要... ...
  • python爬蟲瀏覽器偽裝 #導入urllib.request模塊 import urllib.request #設置請求頭 headers=("User-Agent","Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, l ...
  • 前端代碼搭建 主要利用的是bootstrap3中js插件里的模態框版塊 <li><a href="" data-toggle="modal" data-target=".bs-example-modal-lg">修改密碼</a></li> <div class="modal fade bs-exam ...