?

單源最短路模板題，這里嘗試用SPFA，但有幾點細節：

①不能用鄰接矩陣，開不下1e5*1e5的二維數組；鄰接表vector<p>G[maxn]或鏈式前向星

②注意用longlong，而且INF定義為LONG_LONG_MAX（不要手打整數，因為默認為int，也可強制類型轉換(1e16)）

復習：long double,unsigned long long...log

1e16 ?double ?

999999999999999... ?int（溢出）

?

③最短路算法復習：

a.Dijkstra??

一開始覺得和Prim很像，都用到貪心，而且選好點后，更新與這點相關（可到達）的數據，但是貪心的對象有細微不同。

Prim是dis一維數組（表示目前已加入生成樹的點，到其相鄰結點的權值的最小值）進行貪心，沒有dp的思想；

Dijkstra對松弛操作的dis一維數組（表示起點到該點的最小距離，還要加上前面已經得到的最小距離，而前面得到局部最小距離，必須也是全局最小距離，這是算法成立的關鍵，也是為什么Dijkstra只支持非負邊，這里最優子結構的思想，類似dp）貪心，取出最小所在的的結點P，然后對該點P鄰點(這里類似廣搜)，更新數據，vis標記該點P，最后往復上述操作直到所有vis的點被標記上。

dis? ?1? ????2 ????3 ? ? ?4???? 5???? 6? ? ?（綠色表示當前取得，紅色表示vis標記過已經取過的點，藍色代表更新的點）

? ? ? ?0? ? ? 7????? 9?????∞? ???∞???14

? ? ? ?0? ? ?7? ? ? 9? ? ??∞? ? ∞??? 14

? ? ? ?0? ? ?7? ? ? 9? ? ? 22? ? ∞? ?14

????? ?0? ? ?7? ? ? 9? ?? ?20? ? ∞? ?11

? ? ? ?0? ? ?7? ? ? 9? ? ? 20? ? ∞? ?11

? ? ? ?0? ? ?7? ? ? 9? ? ?20? ? 20? ?11

? ? ? ...

?????? 0? ? ?7? ? ? 9? ? ? 20? ? 20? ?11

具體思想看看這篇博客：

點擊打開鏈接

?

b.Floyd

聯想到之前離散數學學的傳遞閉包Warshall求法：

①k 1-n 找到第k列

②i 1-n? 找到值為1的行，下標i→if(a[i][k]==1)→則執行③j 1-n? ?a[i][j]=a[k][j]

用到三重循環，Floyd與之類似，只不過思想有所改變：

找到第k個結點作為中間點，比較i到j直達的距離和加了中間點k距離。

?

c.

?

最近市面出現了一款全新的游戲，Absolute Counter Online，簡稱ACO。Asuna跟她的男票Kirito也都跑去玩這個了。
? ? 把Kirito傳送了K次之后，Asuna終于氣消了。。。
????最新情報，在這個游戲里，也有傳說中的圣劍excalibur，俗稱咖喱棒。作為耍劍的高手Kirito自然不能放過這么好的一個機會。游戲里有N那個城市，同時有M條道路連接不同的兩個城市，經過不同的道路耗費的時間是不同的。當前Kirito在編號為S的城市，得到的消息是圣劍藏在編號為T的城市中。因為游戲中其他玩家也想搶圣劍，所以Kirito希望用最快的速度到達城市T。而Asuna發現，每個城市中都會有一個傳送用的魔法陣，可以快速將他們傳送到任意一個城市（沒錯，這次他們是兩人一起傳送），不同的魔法陣傳送的用時也不同。

Input

多組數據，EOF結尾。
每組數據先輸入兩個整數N和M，表示有N個城市及M條無向邊。
2 <= N <= 100000
1 <= M <= 200000
接下來一行，輸入N個整數，第i個數字表示城市i的魔法陣，傳送的用時Ui, 1<=Ui<=1000000000。
接下來輸入兩個整數S和T，表示Kirito他們所在城市，以及圣劍所在城市，1<=S,T<=N 且 S!=T。
接下來M行，每行三個整數X, Y, W，表示一條連接X和Y兩個城市的無向邊，通過這條邊的耗時為W，1<=X,Y<=N, X!=Y, 1<=W<=1000000000。
?

Output

對于每組數據，輸出格式為：“Case #k: u”，k表示第k組數據，從1開始，u表示最短用時。

Sample Input

4 3 1 2 3 4 1 4 1 2 1 2 3 1 3 4 1 4 3 10 2 3 4 1 4 2 1 1 2 3 1 3 4 1

Sample Output

Case #1: 1 Case #2: 3

?

#include <stdio.h> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int maxn=300001; const long long inf =(long long)(1e16); //不能直接打數字！！！默認是int會WA struct edge { int from,to,next; long long w; }e[1000001]; int head[maxn]; int vis[maxn]; int vis2[maxn]; long long dist[maxn]; long long mo[maxn]; int n,m,t; void add(int i,int j,long long w) { e[t].from=i; e[t].to=j; e[t].w=w; e[t].next=head[i]; head[i]=t++; } long long spfa(int s,int end,int n) { queue <int> q; for(int i=1;i<=n;i++) dist[i]=inf; memset(vis,false,sizeof(vis)); memset(vis2,false,sizeof(vis2)); q.push(s); dist[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(dist[v]>dist[u]+e[i].w) { dist[v]=dist[u]+e[i].w; if(!vis[v]) { vis[v]=true; q.push(v); } }} } long long res= dist[end];for(int i=1;i<=n;i++){res=min(res,dist[i]+mo[i]);}return res;} int main() { int a,b,s,e; long long c;int cnt=1; // scanf("%d%d",&n,&m); while(cin>>n>>m){memset(mo,0,sizeof(mo));t=0; memset(head,-1,sizeof(head)); //memset(dist,0,sizeof(dist));for(int i=1;i<=n;i++){scanf("%lld",&mo[i]);}scanf("%d%d",&s,&e); while(m--) { scanf("%d%d%lld",&a,&b,&c); add(a,b,c); add(b,a,c);} long long res1= spfa(s,e,n); printf("Case #%d: %lld\n",cnt,res1);cnt++;}return 0; }

?

總結

以上是生活随笔為你收集整理的%大赛D--链式前向星+SPFA（BFS）+各种数据类型+各种最短路复习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。