首页 > 代码库 > [关于最短路的一些小结]
[关于最短路的一些小结]
以前感觉Dijkstra没jb用 今天做了几道题感觉到了一点用处 首先他是在处理密集的图的时候比Spfa会快一点
时间是O(Nlogn)好像 然后有一道题Spfa跑了一分钟Dijkstra 0.1s 忘了什么题
所以Dijksta还是有点用的
其实在这里只想讲一点Dijkstra小的优化而已 并没有打算讲太多东西
1.用堆优化 sb都会写不会看白书(巫泽俊写的) P102-P103
2.其实这个优化不知道Spfa可不可以用 好像也可以，像往常一样 先给道例题 bzoj2200
这道题有单向边 有双向边 然后双向边是可以构成很多个联通块 单向边是连接联通块的单向边(无环)
直接草 抱歉超时 慢很多倍 那么我们可不可以考虑一个个联通块草 使得整个堆变小
这样的话我们先把双向边缩成联通块后 整个图就变成了DAG
然后按照拓扑序将联通块一块块合并起来 怎么说好呢 不算是合并 也就是一块块去做这个意思咯
对于单向边连的两块 影响就一个点 立即更新一下新联通块的点 但是很有可能这两块有很多个单向边连起来
然后再去做新的联通块 当然一开始有些联通块去不了的 你照样放进跑就好 反正也跑不了多少
但是有起点的联通块不一定入度不为0 所以的话 有起点的联通块 一定要从起点开始往外扫 不能从连入这个联通块的点扫(没意义)
#include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<algorithm> #include<queue> #define Maxn 26000 using namespace std; struct node { int x,y,d,next; }edge[Maxn*10]; int len,first[Maxn]; void ins(int x,int y,int d) { len++; edge[len].x=x; edge[len].y=y; edge[len].d=d; edge[len].next=first[x]; first[x]=len; } int N,R,P,ST; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q; queue<int>S; int dis[Maxn]; int fa[Maxn]; int Find(int x){if(x==fa[x]) return fa[x]; else return fa[x]=Find(fa[x]);} int Hash[Maxn]; int cnt; int X[Maxn*2],Y[Maxn*2],D[Maxn*2]; vector<int>V[Maxn]; vector<int>BL[Maxn]; int ru[Maxn]; int main() { freopen("roadplane.in","r",stdin); freopen("roadplane.out","w",stdout); scanf("%d%d%d%d",&N,&R,&P,&ST); len=0; memset(first,-1,sizeof(first)); for(int i=1;i<=N;i++) fa[i]=i; for(int i=1;i<=R;i++) { int x,y,d; scanf("%d%d%d",&x,&y,&d); ins(x,y,d); ins(y,x,d); fa[Find(x)]=Find(y); } for(int i=1;i<=N;i++) if(fa[i]==i) Hash[i]=++cnt; for(int i=1;i<=N;i++) fa[i]=Find(fa[i]); for(int i=1;i<=P;i++) { scanf("%d%d%d",&X[i],&Y[i],&D[i]); V[Hash[fa[X[i]]]].push_back(i); ru[Hash[fa[Y[i]]]]++; BL[Hash[fa[Y[i]]]].push_back(Y[i]); } memset(dis,63,sizeof(dis)); dis[ST]=0; while(!S.empty()) S.pop(); for(int i=1;i<=cnt;i++) if(ru[i]==0) S.push(i); for(int i=1;i<=N;i++) if(fa[i]==i&&ru[Hash[fa[i]]]==0) BL[Hash[fa[i]]].push_back(i); BL[Hash[fa[ST]]].push_back(ST); while(!S.empty()) { int now=S.front(); S.pop(); for(int i=0;i<BL[now].size();i++) { int p=BL[now][i]; Q.push(make_pair(dis[BL[now][i]],BL[now][i])); } while(!Q.empty()) { pair<int,int> x=Q.top(); Q.pop(); if(dis[x.second]<x.first) continue; for(int k=first[x.second];k!=-1;k=edge[k].next) { int y=edge[k].y; if(dis[y]>dis[x.second]+edge[k].d) { dis[y]=dis[x.second]+edge[k].d; Q.push(make_pair(dis[y],y)); } } } for(int i=0;i<V[now].size();i++) { int p=V[now][i]; ru[Hash[fa[Y[V[now][i]]]]]--; if(ru[Hash[fa[Y[V[now][i]]]]]==0) S.push(Hash[fa[Y[V[now][i]]]]); dis[Y[V[now][i]]]=min(dis[Y[V[now][i]]],dis[X[V[now][i]]]+D[V[now][i]]); } } for(int i=1;i<=N;i++) { if(dis[i]<99999999) printf("%d\n",dis[i]); else printf("NO PATH\n"); } return 0; } /* 6 3 3 4 1 2 5 3 4 5 5 6 10 3 5 -100 4 6 -100 1 3 -10 */
然后还有一些题是最短路导航在线改边的(不是你们想象的在线 而是走一步路 最短路就更改)
这种题从终点扫过来就好 很难讲自己意会 例题bzoj 3538
此短路的话就多一个数组记录一下 上次的次短路加上这条边？ 最短路被更新时是否次短路被更新？ 最短路没被更新次短路会被更新？
想一下就好 我也是自己YY的 可能会想多了情况 我不负责 例题bzoj 1726
还有最近超热门的分层图 强烈要求分层图要用Dijkstra+Heap写 不然吃屎我不负责 例题bzoj 1579
求各点间 路径和 加上 路径上的点权的最大值？ Floyd简单O(N^4)可以写 就是枚举点权最大值 其实还有O(N^3)的写法
就是把点按照点权从小到大排 然后每一次k枚举的都是点权从小到大的点 那么你i到j最大值肯定是i或者j或者k 而以k作跳板 也就是F[i][k] F[k][j]这些路径中的点的最大值一定不会超过当前的点权(除两个端点除外) 例题bzoj 1774
还有一些反人类的floyd的题 边数比点数大... 就按边的两端的点离散化一下做就好了 其他都没意义 例题bzoj 1706
还有更反人类的 边数比点数大 单向边 然后还一定过某些点 求两点间最短距离之类的 一定过某些点的某些点个数不多 所以关于这些点的正的扫一遍 反着建边扫一遍 然后就知道这些点到其它点的距离 然后枚举中间点就好了 例题bzoj 4093
我说完了
如果你按照这份题表做完了 你会发现 我草我在带你刷bzoj水题 嘻嘻 所以刷完这份题表后记得评论一个 让我知道一下哪些人这么聪明跟我一起刷水题
有问题想题解仔细的也评论就好了
[关于最短路的一些小结]