图论中的memset和0x3f
写此博客的背景
相信有很多同学在看别人图论专题的题解、板子的时候经常看到下面两句：
const int INF = 0x3f3f3f3f;
memset(d, INF, sizeof(d));
或者下面这样：
memset(d, 0x3f, sizeof(d));
很多同学都不明所以，只知道是将d数组中的所有元素初始化成INF，但是至于为什么选用0x3f3f3f3f和函数memset的原理都不清楚，看到别人这样用，自己也这样用，不清楚为什么，于是前几天同学来问我的时候，就出现了以下WA的代码片段：
const int INF = 1e5；
// ...
memset(d, INF, sizeof(d));
以及：
const int INF = 0x3f3f3f3f;
// ...
memset(a, INF, sizeof(a));
memset(b, INF, sizeof(b));
// ...
ans = min(ans, a[i][k] + a[k][j] + b[i][j]);
如果清楚了上面两个问题，这些bug就可以避免。故写此篇博客，讲解下0x3f3f3f3f和memset的原理和使用注意事项。
memset的原理
C++API文档中的解释与函数原型
可以看到该函数本身是用来初始化字符串（该函数位于string.h中，为C语言头文件，故这里的字符串即char数组，而不是C++中的string），但是参数列表中的第一个参数为void*，再加上C语言的一些特性，该函数也可以对其他类型的数组进行初始化，但是会存在一些其他的问题，下面进行说明。
我们知道在C语言中，char类型占1个字节，而int类型占4个字节。memset在对字符串进行初始化时为逐字符初始化，即每个字节都被初始化。同样的，在使用memset对整型数组进行初始化时，会把每个元素的每个字节初始化成ch。
可能干说理论有点迷糊，所以下面结合一段代码解释。
#include <cstdio>
#include <cstring>
int main() {int a[5];memset(a, 1, sizeof(a));for (int i = 0; i < 5; i++) {printf("%d\n", a[i]);}return 0;
}
运行结果：
16843009
16843009
16843009
16843009
16843009
你会发现初始化的结果并不是1。
事实上，16843009写成二进制如下
对应我刚刚在前面说的，一个int类型为4字节，这里如果把这个数的4字节拆开看的话，每一位都是1。也就是说，它会把每一字节都填充上1。
memset(d, 1e5, sizeof(d));
这段代码的问题也就比较明显了，不过需要注意的是，由于为逐字节初始化，所以超过一个字节的内容会被自动截断，也就是说，1e5只会保留它的低8位，也就是10100000。
由于int类型储存位补码，最高位是符号位，当使用1e5对代码进行初始化的时候符号位被置为1，变成了负数。同理，这也就是为什么上面的代码在使用memset时，使用0x3f和0x3f3f3f3f等价的原因，但是。
使用memset初始化一定要慎重，对于整形数组，一般只用来初始化0、-1、0x3f这几个数字，其他的建议使用循环初始化，初始化其他值时尽量用for来初始化，或者使用fill函数和fill_n函数。
0x3f3f3f3f的原理
0x是16进制的标志，0x3f3f3f3f表示的十进制和二进制见下图。
作为无穷大，一个数除了要保证足够大外，还要保证不能溢出。
使用上面这个值的主要原因是，两个0x3f3f3f3f的和只比int类型的最大值小一点，这样在两个无穷相加时能够保证不会溢出。
同理，对于long long类型，可以使用0x3f3f3f3f3f3f3f3f来进行初始化
这个原理知道了之后就能解释为什么刚刚上面的第二段WA掉的代码问题在哪了：
取0x3f3f3f3f作为INF的话，只能保证两个INF相加不会溢出，但是三个INF就会溢出了，在下面这段代码的min中实际上三个数的和可能为负，导致结果错误。
ans = min(ans, a[i][k] + a[k][j] + b[i][j]);
这里可以加一个判断条件，或者适当降低INF的值，来避免这个问题。
总结
- 使用memset初始化一定要慎重，一般只用来初始化0、-1、0x3f这几个数字，其他的建议使用循环初始化，其他值尽量用
for循环吧。 - 作为无穷大，一个数除了要保证足够大外，还要保证不能溢出。
使用0x3f3f3f3f作为INF主要原因是，两个0x3f3f3f3f的和只比int类型的最大值小一点，这样既能保证一般情况下的足够大，在两个无穷相加时还能够保证不会溢出。
