今天在做一道关于Dijkstra最短路径问题AcWing 849的题目时发现一个有趣的问题。我对正无穷的定义是Integer.MAX_VAULE,有一组数据我得到的结果是负值？！很显然，我数据越界了。再看yxc大神的模板，他对正无穷的定义是0x3f3f3f3f。那么问题来了，为什么要把正无穷定义为0x3f3f3f3f？

题目中如果有明确要求，那么正无穷的设定不是问题，例如AcWing 849中说明图中涉及边长均不超过10000。但是在不明确的情况下，我们习惯将正无穷设为0x7fffffff，因为这是32bit int值的最大值，但是这并不是一个很好的选择。很多时候我们并不只用最大值来做比较，还会先进行运算后再做比较，例如在大部分最短路径算法中都会使用松弛操作dist[j] = Math.min(dist[j], dist[t] + g[t][j])。如果t和j之间没有边，取正无穷等于0x7fffffff，再加上distance[j]就越界变成了负数。所以我们用0x3f3f3f3f来替代。0x3f3f3f3f是十进制1061109567，也是10^9和0x7fffffff一个级别。一般情况下数据都不会大于10^9, 所以可以用来定义正无穷。另一方面，0x3f3f3f3f加上一个数也不会越界，它满足一个重要的性质，“正无穷加上正无穷还是正无穷”。0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但也没有超过32bit int的表示范围。最后，对用C++写代码的同学还有一点方便，如果我们想对某个数组全部赋值为正无穷时，例如图论问题邻接矩阵的初始化，可以使用memset(a, 0x3f ,sizeof(a))，不用手写循环了。

综上，在一般情况下用0x3f3f3f3f定义正无穷是一个不错的选择。