单源最短路模板（dijkstra）

单源最短路（dijkstra算法及堆优化）

n^2 dijkstra模板

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int i,j,n,m,s,dis[];

 bool v[];

 struct Node{

     int to;

     int w;

     Node *next;

 } node[];

 Node *head[];

 int main()

 {

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

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

     {

         dis[i]=0x7fffffff;

         head[i]=new Node;

         head[i]->next=NULL;

     }

     int x,y,w;

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

     {

         scanf("%d%d%d",&x,&y,&w);

         Node *p=new Node;

         p->next=head[x]->next;

         head[x]->next=p;

         p->to=y;

         p->w=w;

     }

     for(Node *h=head[s]->next;h;h=h->next)

         dis[h->to]=min(dis[h->to],h->w);　　　　//注意可能有重边

     v[s]=;

     dis[s]=;

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

     {

         int k=-,minn=0x7fffffff;

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

          if(!v[j]&&dis[j]<minn)

          {

             minn=dis[j];

             k=j;

          }

         if(k==-) break;

         v[k]=;

         for(Node *h=head[k]->next;h;h=h->next)

             if(!v[h->to]&&dis[h->to]>dis[k]+h->w)

             dis[h->to]=dis[k]+h->w;

     }

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

     printf("%d ",dis[i]);

     puts("");

     return ;

 }

毒瘤标准版

题目链接：https://www.luogu.org/problemnew/show/P4779

直到做了这个题才发现我之前写的堆优化dijkstra一直是错的。。

这个堆优化其实很容易理解，将枚举最小值改为从堆中取出最小值，改变dis时入堆即可

用优先队列维护时必须有两个值：点的编号和当前的距离

以距离为标准从小到大排序，每次取出最小的

以前错的原因：

堆中只维护了点的编号，以dis[x]排序

这样做在取出一个元素操作后，会更新它周围一圈元素的dis值，

若它周围一圈元素中有的在堆中，dis值被改变后，堆的性质会遭到破坏

然而由于弱化版太水了，我在做毒瘤版之前一直认为这是对的

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 using namespace std;

 #define il inline

 #define re register

 #define N 100010

 #define M 200010

 int n,m,s,dis[N];

 struct NODE{

     int p;

     int cost;

 };

 struct cmp{

     il bool operator()(NODE ZYX,NODE YSH){

         return ZYX.cost>YSH.cost;

     }

 };

 priority_queue<NODE,vector<NODE>,cmp> q;

 il int read(){

     int x=; char c=getchar();

     while(c<''||c>'') c=getchar();

     while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

     return x;

 }

 void write(int x){

     if(x>) write(x/);

     putchar(x%+'');

 }

 struct NODE{

     int to,w,next;

 } e[M];

 int Head[N],num;

 il void add(int x,int y,int w){

     e[++num].to=y;

     e[num].w=w;

     e[num].next=Head[x];

     Head[x]=num;

 }

 bool used[N];

 int main()

 {

     n=read(); m=read(); s=read();

     int x,y,w;

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

         x=read(); y=read(); w=read();

         add(x,y,w);

     }

     memset(dis,,sizeof(dis));

     dis[s]=;

     q.push((NODE){s,});

     while(!q.empty()){

         NODE k=q.top();

         q.pop();

         int u=k.p;

         if(used[u]) continue;

         used[u]=;

         for(re int i=Head[u];i;i=e[i].next){

             int v=e[i].to;

             if(dis[v]>dis[u]+e[i].w){

                 dis[v]=dis[u]+e[i].w;

                 q.push(NODE{v,dis[v]});

             }

         }

     }

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

      write(dis[i]),putchar(' ');

     return ;

 }

秒客网

单源最短路模板（dijkstra）

相关文章