一、单源最短路(无负权）
1.BFS（无边权）
2.dijkstra(暴力）
#include<bits/stdc++.h> #define ll long long using namespace std; ll dis[101290],n,m,s; bool vis[101001]; vector<pair<int,int>> g[10005]; void d(){ memset(dis,0x3f,sizeof(dis)); dis[s]=0; for(int i=1;i<=n;i++){ ll minx = 0x3f3f3f3f,u; for(int j=1;j<=n;j++){ if(dis[j]<minx&&vis[j]==false) minx=dis[j],u=j; } vis[u]=true; for(int j=0;j<g[u].size();j++){ int y=g[u][j].first,z=g[u][j].second; if(dis[y]>dis[u]+z) dis[y]=dis[u]+z; } } } int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; g[x].push_back({y,z}); } d(); for(int i=1;i<=n;i++){ if(vis[i]==0) cout<<(1<<31)-1<<' '; else cout<<dis[i]<<' '; } return 0; }
2.dijkstra(m log n） 优化查找部分
#include<bits/stdc++.h> using namespace std; int n,m,vis[101009]; vector<int> a[100100]; struct qwerty{ int x,st; }; queue<qwerty> q; long long bfs(){ q.push({1,0}); vis[1]=1; while(!q.empty()){ qwerty n1=q.front(); q.pop(); if(n1.x==n) return n1.st; for(int i=0;i<a[n1.x].size();i++){ qwerty n2={a[n1.x][i],n1.st+1}; if(vis[n2.x]==0){ q.push(n2); vis[n2.x]=1; } } } return 3521; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; a[x].push_back(y); a[y].push_back(x); } cout<<bfs(); return 0; }
二、单源最短路(有负权）
1.bellman-ford(n*m)
负权用dijkstra会崩。
#include <bits/stdc++.h> #include <bits/c++config.h> #include <ostream> #include <istream> #include <algorithm> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <string> #include <math.h> #include <time.h> #include <ctime> #include <cstdlib> #define ll long long #define ull unsigned long long #define db double #define st string #define ch char #define bo bool #define s1 27 #define s2 205 #define s3 2005 #define s4 20005 #define s5 200005 #define s6 2000005 #define s7 20000005 using namespace std; int n,m,s,dis[s5]; vector< pair<int,int> > g[s5]; bool bell(){ memset(dis,0x7f,sizeof(dis)); dis[1]=0; bool f=0; for(int i=1;i<=n;i++){ f=0; for(int j=1;j<=n;j++){ for(int k=0;k<g[j].size();k++){ int v=g[j][k].first; int w=g[j][k].second; if(dis[j]!=0x7f7f7f7f&&dis[j]+w<dis[v]){ dis[v]=dis[j]+w; f=1; } } } } return f; } signed main(){ int T; cin>>T; while(T--){ cin>>n>>m; for(int i=1;i<=n;i++){ g[i].clear(); } for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; if(w<0){ g[u].push_back({v,w}); } else{ g[u].push_back({v,w}); g[v].push_back({u,w}); } } if(bell()){ cout<<"YES\n"; } else{ cout<<"NO\n"; } } return 0; }
2.SPFA(n~nm)
#include <bits/stdc++.h> #include <bits/c++config.h> #include <ostream> #include <istream> #include <algorithm> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <string> #include <math.h> #include <time.h> #include <ctime> #include <cstdlib> #define ll long long #define ull unsigned long long #define db double #define st string #define ch char #define bo bool #define s1 27 #define s2 205 #define s3 2005 #define s4 20005 #define s5 200005 #define s6 2000005 #define s7 20000005 using namespace std; int n,m,s,dis[s5]; vector< pair<int,int> > g[s5]; bool spfa(){ queue<int> q; memset(dis,0x7f,sizeof(dis)); bool iq[s5]={0}; int c[s5]={0}; dis[1]=0; q.push(1); while(!q.empty()){ int u=q.front();q.pop(); iq[u]=0; for(int i=0;i<g[u].size();i++){ int v=g[u][i].first; int w=g[u][i].second; if(dis[u]+w<dis[v]){ dis[v]=w+dis[u]; c[v]=c[u]+1; if(c[v]>=n) return 1; if(!iq[v]){ q.push(v); iq[v]=1; } } } } return 0; } signed main(){ int T; cin>>T; while(T--){ cin>>n>>m; for(int i=1;i<=n;i++){ g[i].clear(); } for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; if(w<0){ g[u].push_back({v,w}); } else{ g[u].push_back({v,w}); g[v].push_back({u,w}); } } if(spfa()){ cout<<"YES\n"; } else{ cout<<"NO\n"; } } return 0; }
二、多源最短路
1.floyd(n^3)(DP)
状态：dp[k][i][j]:i到j最多经过前k个点的最小距离。
状态转移方程：dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]);
空间优化：少一维k。
#include <bits/stdc++.h> #include <bits/c++config.h> #include <ostream> #include <istream> #include <algorithm> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <string> #include <math.h> #include <time.h> #include <ctime> #include <cstdlib> #define ll long long #define ull unsigned long long #define db double #define st string #define ch char #define bo bool #define s1 27 #define s2 205 #define s3 2005 #define s4 20005 #define s5 200005 #define s6 2000005 #define s7 20000005 using namespace std; int n,m,dp[101][101],g[101][101]; signed main(){ cin>>n>>m; memset(g,0x3f,sizeof(g)); for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; g[y][x]=min(g[y][x],z); g[x][y]=min(g[x][y],z); } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dp[i][j]=g[i][j]; if(i==j) dp[i][j]=0; } } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]); } } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<dp[i][j]<<' '; } cout<<'\n'; } return 0; }
