)
{
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
*/View Code
然后还有一些题是最短路导航在线改边的(不是你们想象的在线 而是走一步路 最短路就更改)
这种题从终点扫过来就好 很难讲自己意会 例题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
还有一些比较烦人的负环问题 白书上写的用Bellman-Ford来解决 其实我解决有两种办法
1.在SPFA上判断一个点有没有进入N次 这个很容易证 进入N次就代表有负环了
2.用DFS判断负环如果这个点DFS到一个已经进栈的点 那就有问题了
void Dfs(int x)
{
mark[x]=true;
for(int k=first[x];k!=-1;k=edge[k].next)
{
int y=edge[k].y;
if(dis[y]>=dis[x]+edge[k].d)
{
if(mark[y]){Flag=1; return ;}
else
{
dis[y]=dis[x]+edge[k].d;
Dfs(y);
}
}
}
mark[x]=false;
}
for(int i=1;i<=N;i++) {Dfs(i); if(Flag) return 1;}
这种方法好像比较快比较爽 但是还是习惯了用第一种
还有一些比较新的题 也就是分数规划 什么是分数规划 也就是说 题目要经过的点权和边权的比最小 那么就用到了
首先二分比值 然后把点权弄在边上 用比值乘于边权 也就是说现在的边权就是:(点权-边权*k) (自己写一写移项可得)
这样我们发现 当跑出来大于等于0是 k是合法的 不然不合法 但是我们很难判断是不是有合法 所以我们把边权取反 如果有一个负环 就证明有一条路是合法的
例题bzoj 1690
还有就是 其实最短路和差分约束系统是很相近的 他们有共同的东西 简单提一下
其实我们要化成A+C>=B (C是常数) 也就是说B比A最多大C 这样选最小的c 就是约束了
我只讲了点片面重点的 具体百度
A1-A0<=C 那么就可以移项变成 A0 -> A1 花费为C
A1-A0>=C A1->A0 花费为-C
然后画图 分类讨论一下就好了 例题bzoj 1731
再给一道比较妙的题 bzoj1698
spfa最短路径次数直接跑是不行的 原因有如下:
1.有1到1的情况 也就是先从一个1走到另一个1 再从另一个1走到1 代价不会变
所以这样的话我就想到了把荷叶变成联通块判断这种情况 但是还有..
2.打个比方:
0 0 y 0 0
1 0 0 0 1
0 0 x 0 0
x和y都是清水 从x去到y 可以经过左边的联通块去 可以经过右边的联通块去 答案有两种但其实就只有x,y放荷叶一种
这样处理想起来要解决其实很麻烦 所以我不会去看题解了
题解很简单 先想想 就是x到y所有路径之间都是1 但是不同的联通块 那么我们换位思考 那些不同的联通块连的荷叶点是不是都可以互相到达 然后花费为1
答案是的 所以的话 我们忽略联通块 就把联通块所能去到的荷叶点连起来就好了 但是这样连注意判重
其实下次看到这种题要想想那些不需要的可不可以删掉 来把图变得简单一点
还有一些跨点建边的 也就是A->B B->C A可以到达C且免费 这样跑偷懒最多可以K次 这道题是亲身经历的 GDOI2015 Day2 第一题 当时随便草了个分成图 然后还上去讲了 最后只有30分..
就是因为边目录的时候不可以直接A->C 不然就会以C为跳板去到 A->C C->D A->D...
这个点 打边目录的孩子注意以下就好了 印象深刻 处理方法就是判断这一条边是不是新搞过出来的 其实还有一种特殊的建边方式 可以省边 但是我忘了 可以自己上网搜脑补
最后的话总结一下 就是判负环 DAG拓扑优化 任意两点边权加点权最小值或者最大值 分数规划 差分约束 分层图 在线导航 几乎就是这些了最短路
我说完了
如果你按照这份题表做完了 你会发现 我草我在带你刷bzoj水题 嘻嘻 所以刷完这份题表后记得评论一个 让我知道一下哪些人这么聪明跟我一起刷水题
有问题想题解仔细的也评论就好了