又是好久沒有寫題解了。。。。。 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;
}
代碼的解釋已經在註釋中給出了，如果有不明白歡迎私信我!
