C++中long long类型vector与int类型vector的内存占用异常问题咨询

一、为什么int类型vector反而内存暴涨？ #

这绝对是整数溢出导致的无限入队问题，和vector本身的类型内存大小关系不大！

你回忆下，当用int类型的cost数组时，初始值应该是INT_MAX对吧？在Dijkstra的松弛判断里：

if(cost[curnode] + x.first < cost[x.second])

如果cost[curnode]已经是INT_MAX，加上任何正权重x.first都会触发整数溢出，结果变成一个负数。这时候负数肯定小于cost[x.second]的初始值INT_MAX，程序就会不断更新这个节点的cost，并反复把它推入优先队列。

优先队列会被无限填充，内存直接被撑爆到测试上限。而换成long long后，LONG_LONG_MAX的值大得多（一般是9e18），你的权重总和根本达不到这个阈值，不会触发溢出，自然也就不会出现无限入队的情况，内存占用就正常了。

你之前误以为是vector扩容或类型本身大小导致的，但本质是溢出引发的逻辑错误——单个long long确实比int占内存，但这里的问题是数据量爆炸，不是单个元素的大小。

二、为什么全局vector要设100000+5？ #

这是个很实用的防越界编程习惯：

• 从你的代码能看出来，题目里的节点编号是从1开始的，最大可能到100000（比如输入的n可能是100000）。
• 如果直接把vector大小设为100000，索引最大只能到99999，访问adjlist[100000]就会触发数组越界，导致未定义行为。
• 多开5个位置是留了冗余空间，既能覆盖1到100000的所有合法节点，还能避免一些意外的边界情况（比如输入的节点编号不小心超出范围，或者题目隐含的节点上限略高），让程序更健壮。

额外小优化建议 #

看你的代码里cost.clear(); cost.resize(100005, LONG_LONG_MAX);其实没必要先clear再resize，直接用cost.assign(100005, LONG_LONG_MAX);或者直接resize就行，clear操作是多余的。另外，全局previous数组初始值为0，你只给起点赋值，用previous[n] == 0判断可达性的逻辑没问题，只要题目里节点编号不从0开始就不会有问题。

内容的提问来源于stack exchange，提问作者alex71