樸素Dijkstra模板

int g[N][N],dist[N],st[N],n; int Dijkstra() {memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<n-1;i++){int t=-1;for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;//找到最近的點st[t]=1;for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);//更新}int ans=dist[n];if(ans==0x3f3f3f3f) return -1;return ans; }

堆優化版的Dijkstra

const int N=1e5*3+10; typedef pair<int,int> PII; int h[N],e[N],ne[N],w[N],idx; int dist[N],n,m,st[N]; void add(int a,int b,int c) {e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int Dijkstra() {memset(dist,0x3f,sizeof dist);dist[1]=0;priority_queue<PII,vector<PII>,greater<PII>>q; q.push({0,1});while(q.size()) {auto temp=q.top(); q.pop();int u=temp.second;if(st[u]) continue;st[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[u]+w[i]){dist[j]=dist[u]+w[i];q.push({dist[j],j});}}}int ans=dist[n];if(ans==0x3f3f3f3f) return -1;return ans; }

Bellman_Ford模板

const int N=1e5+10; struct edge{int a,b,c;}S[N]; int n,m,k,dist[N],backup[N];//n個點,m條邊,選不超過k條邊 int solve() {memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<k;i++){memcpy(backup,dist,sizeof dist);for(int j=1;j<=m;j++){int a=S[j].a,b=S[j].b,c=S[j].c;dist[b]=min(dist[b],backup[a]+c);}}return dist[n]; }

spfa模板

const int N=1e5*2+10; int h[N],e[N],w[N],ne[N],idx; int st[N],dist[N],n,m; void add(int a,int b,int c) {e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int spfa() {memset(dist,0x3f,sizeof dist);dist[1]=0; st[1]=1;queue<int>q; q.push(1); while(q.size()){int u=q.front(); q.pop();st[u]=0;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[u]+w[i]){dist[j]=dist[u]+w[i];if(!st[j]) q.push(j),st[j]=1;}}}return dist[n]; }

spfa()判負環

const int N=1e5*3+10; int h[N],e[N],w[N],ne[N],idx; int st[N],dist[N],cnt[N],n,m;//cnt[i] 表示到i點的最短路的邊數 void add(int a,int b,int c) {e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;} bool spfa() {queue<int>q; for(int i=1;i<=n;i++) q.push(i),st[i]=1;while(q.size()){int u=q.front(); q.pop();st[u]=0;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[u]+w[i]){dist[j]=dist[u]+w[i];cnt[j]=cnt[u]+1;if(cnt[j]>=n) return true;//說明有負環if(!st[j]) q.push(j),st[j]=1;}}}return false; }

floyd模板

const int N=210; int dist[N][N],n; void floyd() {for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); }

入門習題:
849. Dijkstra求最短路 I
850. Dijkstra求最短路 II
853. 有邊數限制的最短路
851. spfa求最短路
852. spfa判斷負環
854. Floyd求最短路

總結

以上是生活随笔為你收集整理的ACM入门之【最短路】的全部內容，希望文章能夠幫你解決所遇到的問題。

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