c++算法模板(二)

<6>最短路问题:

1.      Flored-warshall 算法(n^3)

  for(int k=1;k<=n;k++)

          for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

          if((dis[i][j]>dis[i][k]+dis[k][j]) && (i!=k) && (i!=j) && (k!=j))

          {

                  dis[i][j]=dis[i][k]+dis[k][j];

                  pre[i][j]=pre[k][j];

          }

输出路径函数:

在调用处加上:cout<<s<<” ”;   //s为起点;

void print (int x)

 {

         if(pre[s][x]==0) return ;

         print(pre[s][x]);

         cout<<"->"<<x;

 }

2.      dijkstra算法(n^2)

无优化,用了现写的快读搞定。洛谷的模板题P3371.cin流最后一个点超时,scanf和快读都是可以过的。当数据规模比较大的时候用scanf好咯。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define maxn 10010

#define maxm 500010

using namespace std;

int num,minl,k,n,m,s;

int v[maxn],dis[maxn],head[maxn];

int read()

{

int out=0,fh=1;

char cc=getchar();

if (cc=='-')fh=-1;

while(cc>'9'||cc<'0')cc=getchar();

while(cc>='0'&&cc<='9'){out=out*10+cc-'0';cc=getchar();}

return out*fh;}

/*void write(int x)

{

if(x==0){

putchar('0');

return;}

int num=0;char c[15];

while(x)c[++num]=(x%10)+48,x/=10;

while(num) putchar(c[num--]);

putchar(' ');}  */

struct Edge

{

int next;

int to;

int dis;

}edge[maxm];

void add_edge (int u,int v,int w)

{

num++;

edge[num].next=head[u];

edge[num].to=v;

edge[num].dis=w;

head[u]=num;

}

void dijstra (int v0)

{

for(int i=1;i<=n;i++)

 dis[i]=2147483647;

dis[v0]=0;

for(int i=1;i<=n;i++)

{

           minl=2147483647;

           k=0;

           for(int j=1;j<=n;j++)

           {

                    if(v[j]==0 && minl>dis[j])

                    {

                             minl=dis[j];

                             k=j;

                    }

           }

           v[k]=1;

           for(int i=head[k];i!=0;i=edge[i].next)

           {

                    if(v[edge[i].to]==0 && minl+edge[i].dis<dis[edge[i].to])

                    dis[edge[i].to]=minl+edge[i].dis;

           }

 }

}

int main()

{

cin>>n>>m>>s;

for(int i=1;i<=m;i++)

{

           int u,v,w;

           u=read();

           v=read();

           w=read();

           add_edge(u,v,w);

}

dijstra(s);

for(int i=1;i<=n;i++)

cout<<dis[i]<<" ";

return 0;

 }

3.Dijkstra(堆优化):

实测516ms; 堆优化是指在寻找最近点时,用堆log时间复杂度取点,priority_queue(/优先队列)实现;

较朴素算法,利用了堆,能更快取得最近点;

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int INF=2147483647;

const int maxn=10000+10;

const int maxm=500000+10;

int n,m,s;

int fir[maxn],nxt[maxm],to[maxm],val[maxm],cnt;

void add_edge(int u,int v,int w)

{

    nxt[++cnt]=fir[u];fir[u]=cnt;to[cnt]=v;val[cnt]=w;

}

struct Node {

    int d,id;

    Node(){}

    Node(int d,int id):d(d),id(id){}

    bool operator < (const Node& rhs) const {

        return d>rhs.d;//重载<,方便堆

    }

};

int dis[maxn],vis[maxn];

void Dijkstra(int s)

{

    for(int i=1;i<=n;i++) dis[i]=INF; dis[s]=0;

    priority_queue<Node>Q;

    Q.push(Node(0,s));

    while(!Q.empty()) {

        Node u=Q.top(); Q.pop();

        if(vis[u.id]) continue;//若某个点已经被更新到最优,就不用再次更新其他点

        vis[u.id]=1;

        for(int e=fir[u.id];e;e=nxt[e]) {

            int v=to[e],w=val[e];

            if(u.d+w<dis[v]) {

                dis[v]=u.d+w;

                Q.push(Node(dis[v],v));

            }

        }

    }

}

int main()

{

    scanf("%d%d%d",&n,&m,&s);

    for(int u,v,w,i=0;i<m;i++) {

        scanf("%d%d%d",&u,&v,&w);

        add_edge(u,v,w);

    }

    Dijkstra(s);

    for(int i=1;i<=n;i++) printf("%d ",dis[i]);

    return 0;

}

4.SPFA(无优化):

766ms;

耗时主要原因是可能某个能将更多点尽可能优化的,却放进了队尾;

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int INF=2147483647;

const int maxn=10000+10;

const int maxm=500000+10;

int n,m,s;

int fir[maxn],nxt[maxm],to[maxm],val[maxm],cnt;

void add_edge(int u,int v,int w)

{

    nxt[++cnt]=fir[u];fir[u]=cnt;to[cnt]=v;val[cnt]=w;

}

int dis[maxn],inq[maxn];

void SPFA(int s)

{

    for(int i=1;i<=n;i++) dis[i]=INF; dis[s]=0;

    queue<int>Q;Q.push(s);

    while(!Q.empty()) {

        int u=Q.front(); Q.pop();

        for(int e=fir[u];e;e=nxt[e]) {

            int v=to[e],w=val[e];

            if(dis[u]+w<dis[v]) {

                dis[v]=dis[u]+w;

                if(!inq[v]) Q.push(v);

            }

        }

    }

}

int main()

{

    scanf("%d%d%d",&n,&m,&s);

    for(int u,v,w,i=0;i<m;i++) {

        scanf("%d%d%d",&u,&v,&w);

        add_edge(u,v,w);

    }

    SPFA(s);

    for(int i=1;i<=n;i++) printf("%d ",dis[i]);

    return 0;

}

5.SPFA(SLF优化):

实测497ms; SLF优化是指,当前进队的dis值与队首的dis值比较,<=进队首,否则进队尾,deque(双向队列)实现;

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int INF=2147483647;

const int maxn=10000+10;

const int maxm=500000+10;

int n,m,s;

int fir[maxn],nxt[maxm],to[maxm],val[maxm],cnt;

void add_edge(int u,int v,int w)

{

    nxt[++cnt]=fir[u];fir[u]=cnt;to[cnt]=v;val[cnt]=w;

}

int dis[maxn],inq[maxn];

void SPFA(int s)

{

    for(int i=1;i<=n;i++) dis[i]=INF; dis[s]=0;

    deque<int>Q;

    Q.push_front(s);

    while(!Q.empty()) {

        int u=Q.front(); Q.pop_front(); inq[u]=0;

        for(int e=fir[u];e;e=nxt[e]) {

            int v=to[e],w=val[e];

            if(dis[u]+w<dis[v]) {

                dis[v]=dis[u]+w;

                if(!inq[v]) {

                    if(Q.empty()||dis[v]<=dis[Q.front()]) Q.push_front(v);

                    else Q.push_back(v);

                    inq[v]=1;

                }

            }

        }

    }

}

int main()

{

    scanf("%d%d%d",&n,&m,&s);

    for(int u,v,w,i=0;i<m;i++) {

        scanf("%d%d%d",&u,&v,&w);

        add_edge(u,v,w);

    }

    SPFA(s);

    for(int i=1;i<=n;i++) printf("%d ",dis[i]);

    return 0;

}

总结对于此题而言,时间效率:SPFA(ELF优化)>Dijkstra(堆优)>SPFA>Dijkstra;

实际上SPFA的时间复杂度不够稳定,有些时候易被出题人卡常数,建议使用更稳定的Dijkstra;