算法（建图）

最短路

1.单源最短路

所有边权为正数

i.朴素Dijkstra算法 O(n2)

Tips:稠密图用邻接矩阵写，稀疏图用邻接表写.

1. s[N]表示已确定最短距离的点,dis[i]表示到点i的最短路.

2. dis[1]=0,dis[除1外的所有点]->正无穷

3. for(int i=0;i<n;i++)
   每次取t为不在s中的距离最近的点

4. 用t取更新其他点的距离

#include<bits/stdc++.h>
using namespace std;
const int N=510;

int n,m;
int g[N][N],dis[N];
bool st[N];

int Dijkstra()
{
   memset(dis,0x3f,sizeof(dis));
   dis[1]=0;

   for(int i=1;i<=n-1;i++)
   {
     int t=-1;
     for(int j=1;j<=n;j++)
     {
        if(!st[j]&&(t==-1||dis[j]<dis[t]))
        t=j;
     }
     st[t]=true;
     for(int j=1;j<=n;j++)
     {
       dis[j]=min(dis[j],dis[t]+g[t][j]);
     }
   }

   if(dis[n]==0x3f3f3f3f) return -1;
   else return dis[n];
}

int main()
{
   scanf("%d%d",&n,&m);

   memset(g,0x3f,sizeof(g));

   while(m--)
   {
      int a,b,c;
      scanf("%d%d%d",&a,&b,&c);
      g[a][b]=min(g[a][b],c);
   }

   printf("%d\n",Dijkstra());

   return 0;
}

ii.堆优化的Dijkstra(手写堆或使用优先队列)O(mlogn)

#include<bits/stdc++.h>

using namespace std;

const int N=100010;
typedef pair<int,int> PII;

int h[N],w[N],e[N],ne[N],d[N],idx=1;//邻接表存储,适合稀疏图.

bool st[N];

int n,m;

void add(int a,int b,int c)
{
  e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int Dijkstra()
{
   memset(d,0x3f,sizeof(d));
   d[1]=0;

   priority_queue<PII,vector<PII>,greater<PII>> heap;
   heap.push({0,1});

   while(heap.size())
   {
     auto t=heap.top();

     heap.pop();

     int ver=t.second,dist=t.first;
     if(st[ver]) continue;
     st[ver]=true;

     for(int i=h[ver];i!=-1;i=ne[i])
     {
       int j=e[i];
       if(d[j]>dist+w[i])
       {
         d[j]=dist+w[i];
         heap.push({d[j],j});
       }
     }
   }

   if(d[n]==0x3f3f3f3f) return -1;
   else return d[n];
}

int main()
{
   memset(h,-1,sizeof(h));
   scanf("%d%d",&n,&m);

   while(m--)
   {
     int a,b,c;
     scanf("%d%d%d",&a,&b,&c);
     add(a,b,c);
   }

   printf("%d\n",Dijkstra());

   return 0;
}

存在负权边(图中存在负权回路时无最短路)

i.SPFA算法(无负环时一定可以用SPFA算法)

可看作Bellman_Ford算法的优化(用bfs优化)

#include<bits/stdc++.h>
using namespace std;
n,m,
const int N=1e5+10,INF=0x3f3f3f3f;

int h[N],e[N],w[N],ne[N],idx;
int n,m,dis[N];
bool st[N];

void add(int a,int b,int c)
{
  e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int SPFA()
{
  memset(dis,INF,sizeof(dis));

  dis[1]=0;//这步很容易忘

  queue <int> q;
  q.push(1);
  st[1]=true;

  while(!q.empty())
  {
    int t=q.front();
    q.pop();
    st[t]=false;//这步也很容易忘

    for(int i=h[t];i!=-1;i=ne[i])
    {
      int j=e[i];
      if(dis[j]>dis[t]+w[i])
      {
        dis[j]=d[t]+w[i];
        if(!st[j])
        {
           q.push(j);
           st[j]=true;
        }
      }
    }
  }

  if(d[n]==INF) return -1;
  else return d[n];
}

int main()
{
  scanf("%d%d",&n,&m);

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

  while(m--)
  {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);

    add(a,b,c);
  }

  int ans=SPFA();

  if(ans==-1) puts("impossible");
  else printf("%d\n",ans);

  return 0;
}

ii.Bellman-Ford算法(可以拿来找负环,或拿来做有边数限制的最短路)O(nm)

#include<bits/stdc++.h>
using namespace std;

const int N=510,M=100010;

struct Edge
{
  int a,b,w;
}e[N];

int dis[N],back[N],n,m,k;

int Bellman_ford()
{
  memset(dis,0x3f,sizeof(dis));
  dis[1]=0;

  for(int i=0;i<k;i++)//k表示限制的边数
  {
     memcpy(back,dis,sizeof(dis));
     for(int j=0;j<m;j++)
     {
        int a=e[j].a,b=e[j].b,w=e[j].w;
        dis[b]=min(dis[b],back[a]+w);
     }
  }

  if(dis[n]>0x3f3f3f3f/2) return -1;//存在负权边时一般不用if(dis[n]==0x3f3f3f3f)判断.
  else return dis[n];
}
int main()
{
  scanf("%d%d%d",&n,&m,&k);

  for(int i=0;i<m;i++)
  {
    int a,b,w;
    scanf("%d%d%d",&a,&b,&w);
    e[i]={a,b,w};
  }

  int res=Bellman_Ford();

  if(res==-1) puts("impossible");
  else printf("%d\n",res);

  return 0;
}

2.多源汇最短路

Floyd算法O(n3)

#include<bits/stdc++.h>
using namespace std;

const int N=210,INF=0x3f3f3f3f;
int dis[N][N];
int n,m,q;

void Floyd()
{
  for(int k=1;k<=n;k++)
  {
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=n;j++)
      {
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 
      }
     }
   }
}

int main()
{
  scanf("%d%d%d",&n,&m,&q);
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      if(i==j) dis[i][j]=0;
      else dis[i][j]=INF;//初始化
    }
  }

  while(m--)
  {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    dis[a][b]=min(dis[a][b],c);
  }

  Floyd();

  while(q--)
  {
     int a,b;
     scanf("%d%d",&a,&b);
     if(dis[a][b]>INF/2) puts("impossible");
     else printf("%d\n",dis[a][b]);
  }

  return 0;
}

最后，我莱茵生命天下第一！！！(夹杂私货)