我的输入测试用例文件中的值是这样的，在代码的某个点上，值会超过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(向量<对<int，ll>>树[]，布尔决定[]，lld[]，int路径[](
void dij(向量<对<int，ll>>树[]，布尔决定[]，int d[]，int路径[](
ll d[n]；
int 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的代码运行良好的原因，因为update会产生溢出，因为变量是两个long long类型变量的总和，而这两个类型变量在main()中分配了最大值LLONG_MAX，所以忽略了这一事实。
由于long long不能容纳2*LLONG_MAX，它既没有在用作最小堆的对集合中保持也没有找到该值。因此，迭代器指向集合的末尾，擦除set.end()将在面向long long数据类型的代码中生成未定义的行为，而在面向int的代码中则不会。
将LLONG_MAX替换为1e18，在代码中解决了问题，代码对所有测试文件都能顺利运行。
此外，为了澄清评论中指出的所有原因，我认为我应该澄清，在执行dist.erase(dist.find(p))之前，不检查dist.find(p)是否存在并且不指向集的末尾不会产生任何问题。这是因为这是Dijkstra算法，并且一旦发现update小于previous的次数，则从源计算该更新距离的节点将始终存在于与距离previous配对的集合中。这是因为所有节点最初都是以值10e8输入的，并且随着在while循环的连续迭代中找到这些值而被更新。
以下是工作代码，唯一的区别是我使用的不是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