最短路模板

迪杰斯特拉基础版

不能只记住链式前向星优化过的模板，那只适用于边比较少，点比较多的情况。一旦我们边有重复，点很少可以n^2解决的时候，这种基础版就发挥了很好的作用。

但值得一提的是，基础版的易错点在于边的重复性，必须严格取最小值才行。

甚至起点也会连接起点（caodan)

# include<iostream>
# include<deque>
# include<vector>
# include<map>
using namespace std;
typedef long long int ll;

map<ll,ll>edge[10000+10];
bool book[10000+10];
ll dis[10000+10];

int main ()
{

    int n,m,st;

    cin>>n>>m>>st;

    book[st]=1;

    fill(dis,dis+10000+10,(1ll<<50));

    for(int i=1; i<=m; i++)
    {
        ll x,y,z;

        cin>>x>>y>>z;
        if(edge[x].find(y)==edge[x].end())
        edge[x][y]=z;
        else
         edge[x][y]=min(edge[x][y],z);

    }

    dis[st]=0;

    for(auto it:edge[st])
    {
        dis[it.first]=min(dis[it.first],it.second);
    }

    ll inf=(1ll<<50);

    ll minn=inf;
    int pos;
    for(int i=1; i<=n-1; i++)
    {
        minn=inf;

        for(int i=1; i<=n; i++)
        {
            if(!book[i]&&dis[i]<minn)
            {
                minn=dis[i];
                pos=i;
            }
        }
        book[pos]=1;

        for(auto it:edge[pos])
        {
            if(dis[it.first]>it.second+dis[pos])
            {
                dis[it.first]=it.second+dis[pos];
            }
        }
    }

    for(int i=1; i<=n; i++)
    {
        if(dis[i]<(1ll<<50))
        cout<<dis[i]<<" ";
        else
        cout<<((1ll<<31)-1)<<" ";

    }
    return 0;


}

Bellman-Ford

针对边进行n-1次循环，可以负权。

# include<iostream>
# include<deque>
# include<vector>
# include<map>
# include<queue>
# include<cstring>

using namespace std;
typedef long long int ll;

ll dis[1000000*5+10];
ll inf=(1ll<<31);

typedef struct
{
    int b,e;
    ll w;
} xinxi;
xinxi s[100000*5+10];

ll pre[100000*5+10];

int main ()
{

    int n,m;

    cin>>n>>m;
    int st;

    cin>>st;


    for(int i=1; i<=m; i++)
    {
        cin>>s[i].b>>s[i].e>>s[i].w;

    }

    for(int i=1; i<=n; i++)
    {
        dis[i]=inf;
    }

    dis[st]=0;

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

        for(int i=1;i<=n;i++)
        {
            pre[i]=dis[i];
        }

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

            if(dis[s[i].e]>dis[s[i].b]+s[i].w)
            {
                dis[s[i].e]=dis[s[i].b]+s[i].w;

            }
        }

        int flag=0;

        for(int i=1;i<=n;i++)
        {
            if(pre[i]!=dis[i])
            {
                flag=1;

                break;
            }
        }

        if(!flag)
        {
            break;
        }



    }

    for(int i=1; i<=n; i++)
    {
        if(dis[i]<inf)
            cout<<dis[i]<<" ";
        else
            cout<<(1ll<<31)-1<<" ";


    }


    return 0;


}

SPFA和迪杰斯特拉不同的是，无需优先队列，每个点可以频繁入队，但不会出现队内有某点又进入某点的情况，可以处理负权

# include<iostream>
# include<deque>
# include<vector>
# include<map>
# include<queue>
# include<cstring>

using namespace std;
typedef long long int ll;

struct node
{
    int id;

    ll dis;
};
queue<node>q;

ll inf=(1ll<<50);

ll dis[10000+10];
int len;
int f[5*100000+10];
int nex[5*100000+10];
bool book[10000+10];

typedef struct
{
    int b,e;
    ll w;
}xinxi;
xinxi s[5*100000+10];

void add(int x,int y,int z)
{
    s[len].b=x;

    s[len].e=y;

    s[len].w=z;

    nex[len]=f[x];

    f[x]=len;

    len++;

}
int main ()
{


     memset(f,-1,sizeof(f));

     int n,m;

     cin>>n>>m;

     int st;

     cin>>st;

     fill(dis,dis+10000+10,inf);

     dis[st]=0;

     for(int i=1;i<=m;i++)
     {
         int x,y,z;

         cin>>x>>y>>z;

         add(x,y,z);

     }

     struct node now;

     now.id=st;

     now.dis=0;

     book[st]=1;

     q.push(now);

     while(!q.empty())
     {
         struct node now=q.front();

         book[now.id]=0;
         q.pop();

         int x=f[now.id];

         while(x!=-1)
         {
             if(dis[s[x].e]>dis[s[x].b]+s[x].w)
             {
                 dis[s[x].e]=dis[s[x].b]+s[x].w;

                 if(!book[s[x].e])
                 {
                     struct node tail;
                     tail.id=s[x].e;

                     tail.dis=dis[s[x].e];

                     q.push(tail);

                     book[s[x].e]=1;

                 }
             }

             x=nex[x];

         }
     }


     for(int i=1;i<=n;i++)
     {
      
      if(dis[i]<inf)
        cout<<dis[i]<<" ";
      else
        cout<<(1ll<<31)-1<<" ";
        
     }


    return 0;


}