Dijkstra priority！

 /\* Dijkstra的算法思想：  在所有没有访问过的结点中选出dis(s,x)值最小的x 对从x出发的所有边(x,y),更新 dis(s,y)=min(dis(s,y),dis(s,x)+dis(x,y)) \*/ 下面是热浪的题解： ``` #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<algorithm> #include<queue> #define N 10005 using namespace std; struct sd{ int num,len; bool operator < (const sd &x) const { if(x.len<len) { return true; } return false; } }lin; vector<sd> edge[N]; priority_queue<sd> q; int dis[N]; bool vis[N]; int n,m,s,e; void init(); int main() { init(); return 0; } void init() { scanf("%d%d%d%d",&n,&m,&s,&e); int a; for(int i=1;i<=m;++i) { scanf("%d%d%d",&a,&lin.num,&lin.len); edge[a].push_back(lin); int b=lin.num; lin.num=a; edge[b].push_back(lin); } memset(dis,0x7f7f7f7f,sizeof(dis)); dis[s]=0; vis[s]=true; for(int i=edge[s].size()-1;i>=0;--i)//important {//此处有点不熟练，需要多多理解！ q.push(edge[s][i]); if(dis[edge[s][i].num]>edge[s][i].len) { dis[edge[s][i].num]=edge[s][i].len; } } for(int i=1;i<n;++i)//very important!!! { sd now; while(!q.empty()) { now=q.top(); q.pop(); if(!vis[now.num]) break; } vis[now.num]=true; for(int j=edge[now.num].size()-1;j>=0;--j) { if(!vis[edge[now.num][j].num]&&dis[edge[now.num][j].num]>dis[now.num]+edge[now.num][j].len) { dis[edge[now.num][j].num]=dis[now.num]+edge[now.num][j].len; sd p; p.num=edge[now.num][j].num; p.len=dis[edge[now.num][j].num]; q.push(p); } } } printf("%d",dis[e]); } ``` #### 下面我们来做一些简单的讲解： 首先，我们需要明白Dijsktra的工作原理，他就是，每次找到当前图中已经更新过最短的点（就是将要被加入vis标记的点），对他的四周相连的点进行更新，然后重复这一过程直到找到最终的点。 详细的算法流程就不再赘述，这里只给一个算法实例（转载）。 ##### 算法实例 先给出一个无向图 图片有问题，这里只能上一个地址了： [无向图](https://pic002.cnblogs.com/images/2012/426620/2012073019593375.jpg) 好像上面的链接还是有问题： 那就见下面的博客吧！ [dalao的博客（DIjsktra入门（普通版））](https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html)  这里我们就主要讲解一下Dijsktra算法相对于普通Dijsktra算法的更新 下面放一个普通版的Dijsktra: ``` #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; struct sd{ int len,num; sd(); sd(int a,int b){num=a; len=b;} bool operator < (const sd & a) const { if(len==a.len) return num<a.num; else len>a.len; } }; int dis[100005],n,m,s; vector<sd> edge[100005]; void Dijsktra() { for(int i=1;i<=n;++i) { dis[i]=2147483647; } dis[s]=0; priority_queue<sd> q; q.push(sd(s,dis[s])); while(!q.empty()) { sd x=q.top(); q.pop(); for(int i=edge[x.num].size()-1;i>=0;--i) { sd y=edge[x.num][i]; if(dis[y.num]>x.len+y.len) { dis[y.num]=x.len+y.len; q.push(sd(y.num,dis[y.num])); } } } } int main() { scanf("%d%d%d",&n,&m,&s); int a,b,c; for(int i=1;i<=m;++i) { scanf("%d%d%d",&a,&b,&c); edge[a].push_back(sd(b,c)); } Dijsktra(); for(int i=1;i<=n;++i) { printf("%d ",dis[i]); } return 0; } ``` 主要区别就是，多了一个起点预处理，因为我们要随时保证优先队列中有一些东西，所以说要先把第一个点的信息处理进去。（见第一篇代码important部分） 然后，后面的其实就一样了，最后还有，当路径被更新后一定不要忘记把更新后的路径扔入priority_queue中 **P.s：一定不要把Dijsktra priorty版和spfa搞混了。SPFA停止条件是当队列为空，而Dijsktra priority和Dijsktra的判停条件是当运行完1~n（n是点数）个点。还有SPFA是队列操作，不是优先队列操作！！！** ##### 特别注意：第一篇代码中标有very important的地方一定是<n不是<=n因为前面预处理第一个点的边的时候，我们相当于已经是循环了一遍了找出最短了！。 ### 今天2.27我发现了更简单的写法！ ``` #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<algorithm> #include<queue> #define N 10005 using namespace std; struct sd{ int num,len; bool operator < (const sd &x) const { if(x.len<len) { return true; } return false; } }lin; vector<sd> edge[N]; priority_queue<sd> q; int dis[N]; bool vis[N]; int n,m,s,e; void init(); int main() { init(); return 0; } void init() { scanf("%d%d%d%d",&n,&m,&s,&e); int a; for(int i=1;i<=m;++i) { scanf("%d%d%d",&a,&lin.num,&lin.len); edge[a].push_back(lin); int b=lin.num; lin.num=a; edge[b].push_back(lin); } memset(dis,0x7f7f7f7f,sizeof(dis)); dis[s]=0; //vis[s]=true; /*for(int i=edge[s].size()-1;i>=0;--i)//important {//此处有点不熟练，需要多多理解！ q.push(edge[s][i]); if(dis[edge[s][i].num]>edge[s][i].len) { dis[edge[s][i].num]=edge[s][i].len; } }*/ sd ti; ti.len=0; ti.num=s; q.push(ti); /* for(int i=1;i<n;++i)//very important!!! { sd now; while(!q.empty()) { now=q.top(); q.pop(); if(!vis[now.num]) break; } vis[now.num]=true; for(int j=edge[now.num].size()-1;j>=0;--j) { if(!vis[edge[now.num][j].num]&&dis[edge[now.num][j].num]>dis[now.num]+edge[now.num][j].len) { dis[edge[now.num][j].num]=dis[now.num]+edge[now.num][j].len; sd p; p.num=edge[now.num][j].num; p.len=dis[edge[now.num][j].num]; q.push(p); } } } */ while(!q.empty()) { sd now; now=q.top(); q.pop(); if(!vis[now.num]) { vis[now.num]=true; for(int j=edge[now.num].size()-1;j>=0;--j) { if(!vis[edge[now.num][j].num]&&dis[edge[now.num][j].num]>dis[now.num]+edge[now.num][j].len) { dis[edge[now.num][j].num]=dis[now.num]+edge[now.num][j].len; sd p; p.num=edge[now.num][j].num; p.len=dis[edge[now.num][j].num]; q.push(p); } } } } printf("%d",dis[e]); } ``` 缩略版如下： ``` #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<algorithm> #include<queue> #define N 10005 using namespace std; struct sd{ int num,len; bool operator < (const sd &x) const { if(x.len<len) { return true; } return false; } }lin; vector<sd> edge[N]; priority_queue<sd> q; int dis[N]; bool vis[N]; int n,m,s,e; void init(); int main() { init(); return 0; } void init() { scanf("%d%d%d%d",&n,&m,&s,&e); int a; for(int i=1;i<=m;++i) { scanf("%d%d%d",&a,&lin.num,&lin.len); edge[a].push_back(lin); int b=lin.num; lin.num=a; edge[b].push_back(lin); } memset(dis,0x7f7f7f7f,sizeof(dis)); dis[s]=0; //vis[s]=true; important！ 这句话一定不能写啊！！！！ sd ti; ti.len=0; ti.num=s; q.push(ti); while(!q.empty()) { sd now; now=q.top(); q.pop(); if(!vis[now.num]) { vis[now.num]=true; for(int j=edge[now.num].size()-1;j>=0;--j) { if(!vis[edge[now.num][j].num]&&dis[edge[now.num][j].num]>dis[now.num]+edge[now.num][j].len) { dis[edge[now.num][j].num]=dis[now.num]+edge[now.num][j].len; sd p; p.num=edge[now.num][j].num; p.len=dis[edge[now.num][j].num]; q.push(p); } } } } printf("%d",dis[e]); } ``` 2018.10.19 上面的DJ们都写的比较假，下面放上一个可以A掉luogu単源最短路径加强版的代码（上面的都应该A不掉）： ``` /* Name: P4779 【模板】单源最短路径（标准版） Copyright: Author: Mudrobot Date: 2018/10/19 20:57:45 Description: Graph Theory (The Shortest Path) */ #include<bits/stdc++.h> #define gc() getchar()//caution!!! #define N 100005 using namespace std; /*inline char gc() { static char buf[1<<18],*fs,*ft; return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++; }*/ template<class T> inline void read(T &aa) { register int k=0,f=1; register char c=gc(); for (;!isdigit(c);c=gc()) if(c=='-')f=-1; for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0'); aa=k*f; } template<class T> inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');} struct sd{ int val,to,next; bool operator < (const sd & njc) const{ return val>njc.val; } sd(){} sd(int a,int b,int c){ next=a;to=b;val=c; } }edge[N*2]; bool vis[N]; int n,m,s,qnt,head[N],dis[N]; void add(int a,int b,int c){ edge[++qnt].next=head[a];edge[qnt].to=b;edge[qnt].val=c;head[a]=qnt; } void Dijkstra(int s){ for(int i=1;i<=n;i++) dis[i]=2147483647; priority_queue<sd> q; dis[s]=0;q.push(sd(0,s,dis[s])); while(!q.empty()){ sd now=q.top();q.pop(); if(vis[now.to]) continue; vis[now.to]=true; for(int i=head[now.to];i;i=edge[i].next){ int v=edge[i].to,val=edge[i].val; if(dis[v]>dis[now.to]+val){ dis[v]=dis[now.to]+val; q.push(sd(0,v,dis[v])); } } } } int main() { //freopen(".in", "r", stdin);freopen(".out", "w", stdout); read(n);read(m);read(s);int a,b,c; for(int i=1;i<=m;++i){ read(a);read(b);read(c); add(a,b,c); } Dijkstra(s); for(int i=1;i<=n;++i) out(dis[i]),putchar(' '); //fclose(stdin);fclose(stdout); return 0; } /* 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 */ ```