c++ - 在 C++ 代码中将数组的数据类型从 int 更改为 long long 并将 INT_MAX 更改为 LLONG_MAX 是如何导致运行时错误的？
问题描述
我的输入测试用例文件中的值使得在代码中的某个点，值会超过 int 的容量，所以我想我会将这个值大于 INT_MAX 的特定数组的数据类型从 int 更改为 long long 和将代码中的最大值从 INT_MAX 更改为 LLONG_MAX，以便运行时的比较不会产生错误的答案。
但是，现在代码似乎在到达上述测试用例之前就遇到了运行时错误。它现在在值都是面向 int 时过去通过的情况下失败。我不明白这怎么可能。
以 int 通过但以 ll 失败的测试用例是：
100 50
1 23 133
1 87 16
2 9 78
3 12 117
3 39 19
5 25 219
5 47 130
5 97 157
6 50 114
9 11 25
9 39 227
10 45 187
10 77 120
12 19 85
13 43 247
14 16 4
15 33 223
16 33 1
19 69 204
20 35 119
20 43 213
20 86 19
22 40 233
23 33 61
23 79 152
26 89 213
27 57 129
28 42 220
31 68 84
31 69 183
32 39 145
32 100 117
33 49 198
34 48 78
37 66 200
37 91 77
39 44 235
41 70 109
42 92 33
44 74 196
48 73 26
51 57 216
53 70 158
63 98 220
66 72 148
80 93 150
81 99 54
83 84 129
83 89 177
95 100 16
下面是在这个 tc 处给出错误的代码。
#include<bits/stdc++.h>
using namespace std;
# define ll long long int
ll update, previous;
set<pair<ll, int>> dist;
auto it=dist.begin();
int ind=0, n, i, j;
pair<ll, int>p;
void dij(vector<pair<int, ll>> tree[], bool decided[], ll d[], int path[]) {
ind=0;
while(!dist.empty()) {
it=dist.begin();
if(it==dist.end()) return;
ind=it->second;
dist.erase(it);
decided[ind]=1;
for(j=0; j<tree[ind].size(); j++) {
update=d[ind]+tree[ind][j].second;
previous=d[tree[ind][j].first];
if(update<previous) {
p=make_pair(previous, tree[ind][j].first);
dist.erase(dist.find(p));
p=make_pair(update, tree[ind][j].first);
dist.insert(p);
path[tree[ind][j].first]=ind;
}
d[tree[ind][j].first]=min(update, previous);
}
}
}
int main()
{
ll edges;
ll x, y, weight;
cin>>n>>edges;
vector<pair<int, ll>> graph[n];
for(i=0; i<edges; i++) {
cin>>x>>y>>weight;
x--; y--;
graph[x].push_back({y, weight});
graph[y].push_back({x, weight});
}
int src=1;
src--;
ll d[n];
for(i=0; i<n; i++) {
if(src==i) {
dist.insert({0, i});
d[i]=0;
}
else {
dist.insert({LLONG_MAX, i});
d[i]=LLONG_MAX;
}
}
bool decided[n]={0};
int path[n]={-1};
for(int i=1; i<n; i++) path[i]=-2;
dij(graph, decided, d, path);
if(path[n-1]==-2) cout<<-1;
else {
vector<int> s;
int final=n-1;
while (final!=-1) {
s.push_back(final);
final=path[final];
}
reverse(s.begin(), s.end());
for(auto pi:s) cout<<pi+1<<" ";
}
cout<<endl;
}
下面是为这个 tc 生成正确输出的代码。
#include<bits/stdc++.h>
using namespace std;
# define ll long long int
ll update, previous;
set<pair<ll, int>> dist;
auto it=dist.begin();
int ind=0, n, i, j;
pair<ll, int>p;
void dij(vector<pair<int, ll>> tree[], bool decided[], int d[], int path[]) {
ind=0;
while(!dist.empty()) {
it=dist.begin();
if(it==dist.end()) return;
ind=it->second;
dist.erase(it);
decided[ind]=1;
for(j=0; j<tree[ind].size(); j++) {
update=d[ind]+tree[ind][j].second;
previous=d[tree[ind][j].first];
if(update<previous) {
p=make_pair(previous, tree[ind][j].first);
dist.erase(dist.find(p));
p=make_pair(update, tree[ind][j].first);
dist.insert(p);
path[tree[ind][j].first]=ind;
}
d[tree[ind][j].first]=min(update, previous);
}
}
}
int main()
{
ll edges;
ll x, y, weight;
cin>>n>>edges;
vector<pair<int, ll>> graph[n];
for(i=0; i<edges; i++) {
cin>>x>>y>>weight;
x--; y--;
graph[x].push_back({y, weight});
graph[y].push_back({x, weight});
}
int src=1;
src--;
int d[n];
for(i=0; i<n; i++) {
if(src==i) {
dist.insert({0, i});
d[i]=0;
}
else {
dist.insert({INT_MAX, i});
d[i]=INT_MAX;
}
}
bool decided[n]={0};
int path[n]={-1};
for(int i=1; i<n; i++) path[i]=-2;
dij(graph, decided, d, path);
if(path[n-1]==-2) cout<<-1;
else {
vector<int> s;
int final=n-1;
while (final!=-1) {
s.push_back(final);
final=path[final];
}
reverse(s.begin(), s.end());
for(auto pi:s) cout<<pi+1<<" ";
}
cout<<endl;
}
两个代码的唯一区别是以下几行：
void dij(vector<pair<int, ll>> tree[], bool denied[], ll d[], int path[])
void dij(vector<pair<int, ll>> 树[], bool 决定[], int d[], int path[])
ll d[n]；
诠释 d[n];
dist.insert({LLONG_MAX, i})
dist.insert({INT_MAX, i})
d[i]=LLONG_MAX
d[i]=INT_MAX
有人可以指出这是如何创建我阅读的以下错误与“在我不应该分配内存的地方”或“尝试使用不是从 new 获得的指针值执行删除”有关的。是什么导致了这个问题，我应该如何解决它？
free(): invalid pointer
Aborted (core dumped)
解决方案
这个问题确实与问题有关long long，这就是为什么代码运行良好的原因，因为会产生溢出int的事实，因为变量是两个类型变量的总和，这两个类型变量会被分配最大值被忽略。updatelong longLLONG_MAXmain()
由于long long无法容纳2*LLONG_MAX，它既没有持有也没有在用作最小堆的对集中找到该值。因此迭代器指向集合的末尾，擦除set.end()将在面向数据类型的代码中产生未定义的行为，而在long long面向代码中则不会int。
取而代之LLONG_MAX的1e18是，在代码中解决了问题，并且所有测试文件的代码都可以顺利运行。
此外，为了澄清通过评论指出的所有原因，我认为我应该澄清dist.find(p)在执行之前不检查是否存在并且不指向集合结束dist.erase(dist.find(p))不会产生任何问题。这是因为它是 Dijkstra 算法，并且只要update发现小于previous，计算此更新距离的节点，从源将始终存在于与距离配对的集合中previous。这是因为所有节点最初输入的10e8值为
下面是工作代码，唯一的区别是LLONG_MAX我没有使用1e18它，它在所有测试文件上运行良好，包括我在问题中提到的有问题的文件。
#include<bits/stdc++.h>
using namespace std;
# define ll long long int
ll update, previous;
set<pair<ll, int>> dist;
auto it=dist.begin();
int ind=0, n, i, j;
pair<ll, int>p;
void dij(vector<pair<int, ll>> tree[], bool decided[], ll d[], int path[]) {
ind=0;
while(!dist.empty()) {
it=dist.begin();
if(it==dist.end()) return;
ind=it->second;
dist.erase(it);
decided[ind]=1;
for(j=0; j<tree[ind].size(); j++) {
update=d[ind]+tree[ind][j].second;
previous=d[tree[ind][j].first];
if(update<previous) {
p=make_pair(previous, tree[ind][j].first);
//cout<<p.first<<" intermediate "<<p.second<<endl;
dist.erase(dist.find(p));
p=make_pair(update, tree[ind][j].first);
dist.insert(p);
path[tree[ind][j].first]=ind;
}
d[tree[ind][j].first]=min(update, previous);
}
}
}
int main()
{
ll edges;
ll x, y, weight;
cin>>n>>edges;
vector<pair<int, ll>> graph[n];
for(i=0; i<edges; i++) {
cin>>x>>y>>weight;
x--; y--;
graph[x].push_back({y, weight});
graph[y].push_back({x, weight});
}
int src=1;
src--;
ll d[n];
for(i=0; i<n; i++) {
if(src==i) {
dist.insert({0, i});
d[i]=0;
}
else {
dist.insert({1e18, i});
d[i]=1e18;
}
}
bool decided[n]={0};
int path[n]={-1};
for(int i=1; i<n; i++) path[i]=-2;
dij(graph, decided, d, path);
if(path[n-1]==-2) cout<<-1;
else {
vector<int> s;
int final=n-1;
while (final!=-1) {
s.push_back(final);
final=path[final];
}
reverse(s.begin(), s.end());
for(auto pi:s) cout<<pi+1<<" ";
}
cout<<endl;
}
这是问题中测试文件的输出：
输入
100 50
1 23 133
1 87 16
2 9 78
3 12 117
3 39 19
5 25 219
5 47 130
5 97 157
6 50 114
9 11 25
9 39 227
10 45 187
10 77 120
12 19 85
13 43 247
14 16 4
15 33 223
16 33 1
19 69 204
20 35 119
20 43 213
20 86 19
22 40 233
23 33 61
23 79 152
26 89 213
27 57 129
28 42 220
31 68 84
31 69 183
32 39 145
32 100 117
33 49 198
34 48 78
37 66 200
37 91 77
39 44 235
41 70 109
42 92 33
44 74 196
48 73 26
51 57 216
53 70 158
63 98 220
66 72 148
80 93 150
81 99 54
83 84 129
83 89 177
95 100 16
参与者的输出
-1
陪审团的回答
-1
提交链接 - Dijkstra
推荐阅读
- django - docker容器中的cronjob无法连接到其他容器
- datetime - Hive：在“yyyy-MM-dd'T'HH:mm:ss.SSS'Z'”中转换缺少秒数的字符串日期时间
- java - 如何从数据库中获取数据？
- r - 使用 as 将整数转换为数字
- python - Matplotlib：保存一个独立的、可编辑的图形
- angular-material - 如何设置 mat-grid-list 的装订线颜色？
- sql - Amazon Athena 分区查询错误“没有可行的替代方案”
- python-3.x - 使用 FlaskForm 进行错误检查和闪烁错误消息
- mongodb - Istio 特使代理问题
- reactjs - 是否可以在调用 REST api 时使用 if 语句？