单源、多源最短路

一、单源最短路(无负权1.BFS无边权2.dijkstra(暴力#includebits/stdc.h #define ll long long using namespace std; ll dis[101290],n,m,s; bool vis[101001]; vectorpairint,int g[10005]; void d(){ memset(dis,0x3f,sizeof(dis)); dis[s]0; for(int i1;in;i){ ll minx 0x3f3f3f3f,u; for(int j1;jn;j){ if(dis[j]minxvis[j]false) minxdis[j],uj; } vis[u]true; for(int j0;jg[u].size();j){ int yg[u][j].first,zg[u][j].second; if(dis[y]dis[u]z) dis[y]dis[u]z; } } } int main(){ cinnms; for(int i1;im;i){ int x,y,z; cinxyz; g[x].push_back({y,z}); } d(); for(int i1;in;i){ if(vis[i]0) cout(131)-1 ; else coutdis[i] ; } return 0; }2.dijkstra(m log n 优化查找部分#includebits/stdc.h using namespace std; int n,m,vis[101009]; vectorint a[100100]; struct qwerty{ int x,st; }; queueqwerty q; long long bfs(){ q.push({1,0}); vis[1]1; while(!q.empty()){ qwerty n1q.front(); q.pop(); if(n1.xn) return n1.st; for(int i0;ia[n1.x].size();i){ qwerty n2{a[n1.x][i],n1.st1}; if(vis[n2.x]0){ q.push(n2); vis[n2.x]1; } } } return 3521; } int main(){ cinnm; for(int i1;im;i){ int x,y; cinxy; a[x].push_back(y); a[y].push_back(x); } coutbfs(); return 0; }二、单源最短路(有负权1.bellman-ford(n*m)负权用dijkstra会崩。#include bits/stdc.h #include bits/cconfig.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 pairint,int g[s5]; bool bell(){ memset(dis,0x7f,sizeof(dis)); dis[1]0; bool f0; for(int i1;in;i){ f0; for(int j1;jn;j){ for(int k0;kg[j].size();k){ int vg[j][k].first; int wg[j][k].second; if(dis[j]!0x7f7f7f7fdis[j]wdis[v]){ dis[v]dis[j]w; f1; } } } } return f; } signed main(){ int T; cinT; while(T--){ cinnm; for(int i1;in;i){ g[i].clear(); } for(int i1;im;i){ int u,v,w; cinuvw; if(w0){ g[u].push_back({v,w}); } else{ g[u].push_back({v,w}); g[v].push_back({u,w}); } } if(bell()){ coutYES\n; } else{ coutNO\n; } } return 0; }2.SPFA(n~nm)#include bits/stdc.h #include bits/cconfig.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 pairint,int g[s5]; bool spfa(){ queueint q; memset(dis,0x7f,sizeof(dis)); bool iq[s5]{0}; int c[s5]{0}; dis[1]0; q.push(1); while(!q.empty()){ int uq.front();q.pop(); iq[u]0; for(int i0;ig[u].size();i){ int vg[u][i].first; int wg[u][i].second; if(dis[u]wdis[v]){ dis[v]wdis[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; cinT; while(T--){ cinnm; for(int i1;in;i){ g[i].clear(); } for(int i1;im;i){ int u,v,w; cinuvw; if(w0){ g[u].push_back({v,w}); } else{ g[u].push_back({v,w}); g[v].push_back({u,w}); } } if(spfa()){ coutYES\n; } else{ coutNO\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/cconfig.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(){ cinnm; memset(g,0x3f,sizeof(g)); for(int i1;im;i){ int x,y,z; cinxyz; g[y][x]min(g[y][x],z); g[x][y]min(g[x][y],z); } for(int i1;in;i){ for(int j1;jn;j){ dp[i][j]g[i][j]; if(ij) dp[i][j]0; } } for(int k1;kn;k){ for(int i1;in;i){ for(int j1;jn;j){ dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]); } } } for(int i1;in;i){ for(int j1;jn;j){ coutdp[i][j] ; } cout\n; } return 0; }