最短路板子

floyed O(n^3)

 f[i][j] = min(f[i][j] ,f[i][k] + f[k][j] )

memset(f,inf,sizeof(f));
     for(i=1;i<=m;i++) cin>>x>>y>>z,f[x][y]=f[y][x]=z;
      
      for(k=1;k<=n;k++)
      for(i=1;i<=n;i++)
       for(j=1;j<=n;j++){
           if(i==j) f[i][j]=0;
            else if(f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j];
        }

Dijkstra （只能处理正权图

该算法用 d[i] 保存起点到其他点的距离，初始为无穷

每次找d[i] 最小的点i ，以此更新 d[y] = min(d[y], d[i]+ len(i,y) )

找最小的 d[i] 可以用优先队列优化一下

#include <iostream>
#include <cstring>
#include <queue>
using namespace std ; 
 struct T{
     int y,z;
     T(int y0,int z0){
         y=y0,z=z0;
     }
     bool operator<(T a)const{
         return z>a.z;
     }
 };
 const int N=1e4+1,M=1e6+1,inf=0x3f3f3f3f;
 int n,b[N],d[N],nxt[M],w[M],go[M],hd[N],all;
 
 void add(int x,int y,int z){
     go[++all]=y,nxt[all]=hd[x];
    hd[x]=all,w[all]=z;
 }
 priority_queue<T> q;
 
 void dijk(int v0){
     int i,x,y,z;
     memset(d,inf,sizeof d); d[v0]=0;
     q.push(T(v0,0));
     
     while(q.empty()==0){
         x=q.top().y,q.pop(); if(b[x]) continue;
         b[x]=1;
         for(i=hd[x];i;i=nxt[i]){
             y=go[i],z=w[i]; 
             if(d[x]+z<d[y]){
                 d[y]=d[x]+z; q.push(T(y,d[y]));
            }
         }
     }
 }
 signed main(){
     int v0,i,x,y,z,m;
     std::cin>>n>>m>>v0;
     for(i=1;i<=m;i++) cin>>x>>y>>z,add(x,y,z);
     
     dijk(v0);
     for(i=1;i<=n;i++) cout<<d[i]<<' ';
 }

SPFA 边权可负

int all,nxt[M],go[M],hd[N],vis[N],w[M];
 int dis[N],n,m;
 
 void add(int x,int y,int z){
     go[++all]=y;
    w[all]=z,nxt[all]=hd[x],hd[x]=all;
 }
 queue<int> q;
 
 void spfa(int v0){
     int i,x,y,z;
     for(i=0;i<=n+1;i++) dis[i]=inf; dis[v0]=0;
     q.push(v0);
     
     while(!q.empty()){
         x=q.front(),q.pop();
         vis[x]=0;
         
         for(i=hd[x];i;i=nxt[i]){
             y=go[i],z=w[i];
             if(dis[y]>dis[x]+z){
                  dis[y]=dis[x]+z;
                  if(!vis[y]) vis[y]=1,q.push(y);
             }
        }
     }
 }