目录

最短路

\(Floyed\)

\(n^3\)复杂度，数据小可以用，也可以用来判断图是否连通、求环。

for(int k=1;k<=n;k++)//注意中转点在最外层枚举    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)             map[i][j]=min(map[i][k]+map[k][j],map[i][j]);

\(SPFA\)

广搜求最短路，容易被卡

#include
    
     #include
     
      #include
      
       using namespace std;struct node{    int next,to,w;}a[500010*5];int cnt,n,m,s,minn=0x7f,head[500010],dis[500010],exist[500010],team[500010*5],u;void SPFA(){    for(int i=1;i<=n;++i) dis[i]=2147483647;    memset(exist,0,sizeof(exist));    int h=0,t=1;    dis[s]=0,exist[s]=1,team[1]=s;    while(h
       
        dis[u]+a[i].w){                   dis[v]=dis[u]+a[i].w;                   if(!exist[v]) exist[v]=1,team[++t]=v;              }    }}int main(){    cin>>n>>m>>s;    for(int i=1;i<=m;++i){         int x,y,z;         cin>>x>>y>>z;         a[++cnt].next=head[x],a[cnt].to=y,a[cnt].w=z,head[x]=cnt;     }    SPFA();    for(int i=1;i<=n;++i)        if(dis[i]==66666) cout<<2147483647<<' ';        else cout<
        
         <<' ';    return 0;}
        
       
      
     
    

\(Dijkstra\)堆优化

比较靠谱的算法。思路就是每次选距离已选点集距离最小的点加入点集

#include
    
     #include
     
      using namespace std;struct Edge{    int v,w,nxt;}e[500010];int head[100010],cnt,n,m,s,dis[100010];inline void addEdge(int u,int v,int w){    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;}struct node{    int u,d;    bool operator <(const node& rhs) const{        return d>rhs.d;    }};inline void Dijkstra(){    for(int i=1;i<=n;++i) dis[i]=2147483647;    dis[s]=0;    priority_queue
      
        Q;    Q.push((node){s,0});    while(!Q.empty()){        node fr=Q.top();Q.pop();        int u=fr.u,d=fr.d;        if(d!=dis[u]) continue;        for(int i=head[u],v;v=e[i].v,i;i=e[i].nxt)            if(dis[u]+e[i].w
      
     
    

二分\(+\)最短路

n个点，p条边，k个机会将边权变成零，求最短路 。二分很好用（耍流氓）。

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);int n,p,k,H[1005],X[20005],P[20005],E[20005],w[20005],d[1005],tot;bool vis[1005];inline void add(int x,int y,int z){    P[++tot]=y,X[tot]=H[x],H[x]=tot,E[tot]=z;}struct N{    int x,w;    N(int a=0,int b=0){x=a,w=b;}    friend bool operator < (N a,N b){        return a.w>b.w;    }};priority_queue
        
          q;bool judge(int lim){    for(int i=1;i<=tot;i++)        if(E[i]>lim) w[i]=1;        else w[i]=0;    memset(d,0x3f,sizeof d);    memset(vis,0,sizeof vis);    d[1]=0,q.push(N(1,0));    int x;    while(!q.empty()){        x=q.top().x,q.pop();        if(vis[x]) continue;        vis[x]=1;        for(int i=H[x];i;i=X[i])            if(!vis[P[i]]&&d[P[i]]>d[x]+w[i]){                d[P[i]]=d[x]+w[i];                q.push(N(P[i],d[P[i]]));            }    }    if(d[n]<=k) return 1;    return 0;}int main(){    scanf("%d%d%d",&n,&p,&k);    for(int i=0,x,y,z;i
         
          >1; if(judge(m)) r=m-1,ans=m; else l=m+1; } printf("%d\n",r); ed:return 0;}
         
        
       
      
     
    

最短路计数

求到每个点有多少条最短路

更新最短路的同时记录有多少条最短路。若有更短的，则条数等于上一个点的最短路条数，若相等则最短路条数\(+1\)

#include
    
     #include
     
      #include
      
       using namespace std;const int mod=100003;int n,m,head[1000005],cnt,dis[1000005],num[1000005];bool vis[1000005];struct node{    int to,next;}a[4000005];long long read(){    long long x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}void add(int x,int y){    a[++cnt].to=y,a[cnt].next=head[x],head[x]=cnt;}void spfa(){    queue
       
        q;    q.push(1),vis[1]=1;    while(!q.empty()){        int u=q.front();q.pop(),vis[u]=0;        for(int i=head[u],v;v=a[i].to,i;i=a[i].next)            if(dis[v]>dis[u]+1){                dis[v]=dis[u]+1,num[v]=num[u]%mod;                if(!vis[v]) q.push(v),vis[v]=1;            }            else if(dis[v]==dis[u]+1) num[v]=(num[v]+num[u])%mod;    } }int main(){    n=read(),m=read();    for(int i=1,x,y;i<=m;++i){        x=read(),y=read();        add(x,y),add(y,x);    }    for(int i=1;i<=n;++i) dis[i]=37022059;    dis[1]=0,num[1]=1;    spfa();    for(int i=1;i<=n;++i) printf("%d\n",num[i]);    return 0;}
       
      
     
    

次短路

这是严格次短路。

考虑在什么情况下会更新最短路。

\(1、\)由父亲节点过来的距离小于最短路，那么当前最短路变成次短路，更新最短路

\(2、\)若当前距离不能更新最短路，但比次短路小，更新次短路

\(3、\)若从父亲节点过来的次短路能更新当前次短路，更新次短路

所以，求次短路只需要一遍\(SPFA\)在更新最短路的时候顺便更新次短路就好了

#include
    
     #include
     
      #include
      
       using namespace std;int n,m,head[5005],cnt,dis[2][5005];bool vis[5005];struct Dier{    int next,to,w;}a[200005];void add(int x,int y,int z){    a[++cnt].next=head[x],a[cnt].to=y,a[cnt].w=z,head[x]=cnt;}long long read(){    long long x=0;int f=0;char c=getchar();    while(c<'0'||c>'9'){f|=c=='-';c=getchar();}    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}    return f?-x:x;}void spfa(){    for(int i=1;i<=n;++i) dis[1][i]=dis[0][i]=214748364;//1：最短路 0：次短路    queue
       
        q;    q.push(1),dis[1][1]=0,vis[1]=1;    while(!q.empty()){        int u=q.front();q.pop(),vis[u]=0;        for(int i=head[u],v;v=a[i].to,i;i=a[i].next){            bool f=0;int w=a[i].w;            if(dis[1][v]>dis[1][u]+w)//第一种情况                dis[0][v]=dis[1][v],dis[1][v]=dis[1][u]+w,f=1;            if(dis[0][v]>dis[1][u]+w&&dis[1][v]!=dis[1][u]+w)//第二种情况                dis[0][v]=dis[1][u]+w,f=1;            if(dis[0][v]>dis[0][u]+w)//第三种情况                dis[0][v]=dis[0][u]+w,f=1;            if(!f||vis[v]) continue;            q.push(v),vis[v]=1;        }    }}int main(){    n=read(),m=read();    for(int i=1,x,y,z;i<=m;++i){        x=read(),y=read(),z=read();        add(x,y,z),add(y,x,z);    }    spfa();    printf("%d",dis[0][n]);    return 0;}
       
      
     
    

\(K\)短路

详情见

我目前不会做。

欢迎指正评论O(∩_∩)O~~