Dijkstra

Dijkstra解决单源最短路的问题 如果有边权为负不可以使用Dijkstra算法。 跑得比SPFA快

算法原理

贪心

我们从起点开始走，因为我们要最快达到终点，所以要选取当前离起点最近的一个点开始走，也就是我们存一个离起点的距离数组。

算法步骤

1. 建图
2. 从起点开始走，每次走的距离都是当前没走过的距离起点最近的路径。
3. 将走后的路径放入到优先队列里面
4. 一直走，直到走完图

Dijistra()

Code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+12,inf=0x3fffffff;
int head[N],dis[N],n,m,cnt,a[N],s;
struct {
  int to,w,nex;
}edge[N];
struct node{
  int v,w;
  bool operator < (const node &other) const
  {
    return other.w<w;
  }
};

priority_queue<node>q;

void addedge(int u,int v,int w)
{
  cnt++;
  edge[cnt].to=v;
  edge[cnt].nex=head[u];
  edge[cnt].w=w;
  head[u]=cnt;
}

void dijstra()
{
  q.push({1,0});
  dis[1]=0;
  while( !q.empty() )
  {
    node z=q.top();
    q.pop();
    int y=z.v,w=z.w;
    if( a[y] ) continue;
    a[y]=1;
    for(int i=head[y];i;i=edge[i].nex)
    {
      if( dis[y]+edge[i].w<dis[ edge[i].to ] )
      {
       dis[ edge[i].to ] =  dis[y]+edge[i].w ;
       if( !a[ edge[i].to ] )
        q.push( {edge[i].to,dis[y]+edge[i].w} );
      }
    }
  }
}

int main(){
 cin>>n>>m;

 for(int i=1;i<=n;i++)
  dis[i]=inf;
int u,v,w;
 while(m--)
 {
   cin>>u>>v>>w;
   addedge(u,v,w);
 }
 dijstra();
 for(int i=1;i<=n;i++)
 {
   cout<<dis[i]<<" ";

 }



}

另类题型

快递员送信 该题要我们解决，快递员从1节点到n节点，并且每到一个节点就会返回1节点求最后一共花了多少时间。

分析：

要解决的问题

1. 快递员从1节点到各个节点所需要的时间
2. 各个节点到1节点的时间
3. 所有时间的总和

解决方法

1. 从1节点开始，向各个节点跑一次最短路，每个节点的路径就是从1节点到他们的时间。
2. 逆向分析，各个节点到1节点的时间，反着来看，就是1节点走反向边道各个节点的时间。
3. 因为快递员送完一个节点就要回到1节点，所以我们将各个节点的值相加就可以了

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+12,inf=1e9+12;
int head1[N],head2[N],a[N],b[N];
int vis1[N],vis2[N],ans,n,m,u,v,w;
int cnt,tot;

struct {
  int to,nex,w;
}e1[N],e2[N];

struct node{
  int v,w;
  bool operator < ( const node &other  )const
  {
    return other.w<w;
  }
};

void addedge1(int u,int v,int w)
{
  cnt++;
  e1[cnt].nex=head1[u];
  e1[cnt].to=v;
  e1[cnt].w=w;
  head1[u]=cnt;
}

void addedge2(int u,int v,int w)
{
  tot++;
  e2[tot].nex=head2[u];
  e2[tot].to=v;
  e2[tot].w=w;
  head2[u]=cnt;
}

priority_queue<node>q;

void dijstra1(){
  q.push({1,0});
  a[1]=0;
  while( !q.empty() )
  {
    node p=q.top();
    q.pop();
    int y=p.v,w=p.w;
    if( vis1[y] ) continue;
    vis1[y]=1,a[y]=w;
    for(int i=head1[y];i;i=e1[i].nex)
    {
      q.push( { e1[i].to,e1[i].w+w } );
    }
  }

}

void dijstra2(){
  q.push({1,0});
  b[1]=0;
  while( !q.empty() )
  {
    node p=q.top();
    q.pop();
    int y=p.v,w=p.w;
    if( vis2[y] ) continue;
    vis2[y]=1,b[y]=w;
    for(int i=head2[y];i;i=e2[i].nex)
    {
      q.push( { e2[i].to,e2[i].w+w } );

    }

  }

}

int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    a[i]=b[i]=inf;
  }
  while(m--)
  {
    cin>>u>>v>>w;
    addedge1(u,v,w);
    addedge2(v,u,w);
  }
  dijstra1();
  dijstra2();
  for(int i=1;i<=n;i++)
    ans+=a[i]+b[i];
  cout<<ans<<endl;



}