洛谷P2299題解:Dijkstra+堆優化

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

又是好久沒有寫題解了。。。。。 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;
}

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


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

更多相關文章
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...