P4779 【模板】单源最短路径(标准版)

链接:P4779

-----------------------------------------

这道题卡了spfa和迪杰斯特拉朴素版

我们要使用优化版才行。

----------------------------------------

优化版是用了个堆来完成的。我们考虑一下,在初始化距离为无穷大后,对于每一个点,分成两类,一类是已经确定的,一类是没有的。对于已经确定的,我们没必要去扫描他。对于没有确定的,再分为两类,靠着一个已确定点的和没有的,那么对于第一类,他是可以确定的,更新的,并可以用它更新其他点。对于第二类,是没有必要的,因为除非身边有一个确定点,否则还是无穷大。朴素的迪杰斯特拉,是扫描每一个点,不可避免地扫描上第一类和第二类的第二类。而用了堆,我们就可以保证只更新第二类的第一类,并且把更新后的点周围的第二类点加进去,就可以优化了

---------------------------------------

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<queue>
 7 using namespace std;
 8 int p;
 9 int head[1000001];
10 int dis[1000001];
11 int vis[1000001];
12 int n,m;
13 int x,y,z;
14 struct b{
15     int to;
16     int v;
17     int next;
18 }bian[5000001];
19 void add(int f,int to,int v){
20     p++;
21     bian[p].next=head[f];
22     bian[p].to=to;
23     bian[p].v=v;
24     head[f]=p;
25 }
26 int s;
27 struct qu{
28     int v;
29     int point;
30     bool operator <(const  qu &b1)const{
31     return b1.v<v; 
32     }
33 };
34 priority_queue<qu> q11;
35 void dij(){
36     dis[s]=0;
37     q11.push((qu){0,s});
38     while(q11.size()){
39         qu now=q11.top();
40         q11.pop();
41         int x=now.point;
42         int bbb=now.v;
43         if(vis[x]){
44             continue;
45         }
46         vis[x]=1;
47         for(int i=head[x];i;i=bian[i].next){
48             int v=bian[i].to;
49             if(dis[v]>dis[x]+bian[i].v){
50                 dis[v]=dis[now.point]+bian[i].v;
51                     q11.push( (qu){ dis[v] ,v});
52             }
53         }
54         
55     }
56 }
57 int main(){
58     //memset(dis,0x7f,sizeof(dis));
59     scanf("%d%d%d",&n,&m,&s);
60     for(int i=1;i<=n;++i)
61     dis[i]=1e10;
62     for(int i=1;i<=m;++i){
63         scanf("%d%d%d",&x,&y,&z);
64         add(x,y,z);
65     }
66     dij();
67     for(int i=1;i<=n;++i){
68         printf("%d ",dis[i]);
69     }
70     return 0;
71 }
Ac
原文地址:https://www.cnblogs.com/For-Miku/p/11262025.html