memset(dist,0x3f,sizeof dist);这句话是什么意思
时间: 2023-06-07 20:08:32 浏览: 283
这句话的意思是将数组dist中的所有元素初始化为0x3f,这是因为0x3f在二进制中表示为11111111,意味着最大值。所以这句话的作用就是将dist数组中的所有元素初始化为一个最大值,以便在后续的算法中能够区分出尚未更新的节点。
相关问题
memset(dist,-1,sizeof(dist))
This line of code uses the memset() function to initialize an integer array named "dist" with -1 values.
The memset() function is commonly used in C/C++ to set a block of memory to a specific value. It takes three arguments- the memory block to be initialized, the value to be set, and the number of bytes to be set. In this case, the memory block is "dist", the value is -1, and the number of bytes is calculated by multiplying the size of an integer with the size of the array "dist".
Therefore, the effect of this line is to set all elements of the "dist" array to -1, effectively initializing it for use in a graph or distance calculation algorithm.
#include <iostream>#include <cstring>#include <deque>using namespace std;const int N = 1000010, M = 2000010;const int INF = 0x3f3f3f3f;int n, m, s, t;int h[N], e[M], ne[M], w[M], idx;int dist[N];bool st[N];int cnt[N];deque<int> q;void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;}bool spfa() { memset(dist, 0x3f, sizeof dist); dist[s] = 0; q.push_back(s); st[s] = true; while (!q.empty()) { int t = q.front(); q.pop_front(); st[t] = false; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) return false; if (!st[j]) { if (!q.empty() && dist[j] < dist[q.front()]) q.push_front(j); else q.push_back(j); st[j] = true; } } } } return true;}int main() { scanf("%d%d%d%d", &n, &m, &s, &t); memset(h, -1, sizeof h); while (m --) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); add(b, a, c); } if (spfa()) cout << dist[t] << endl; else puts("无解"); return 0;}在不用STL容器的前提下实现这个代码
好的,以下是不使用STL容器的实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000010, M = 2000010;
const int INF = 0x3f3f3f3f;
int n, m, s, t;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
int cnt[N];
int q[N];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
bool spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
int hh = 0, tt = 0;
q[tt ++] = s;
st[s] = true;
while (hh != tt)
{
int t = q[hh ++];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return false;
if (!st[j])
{
q[tt ++] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return true;
}
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
memset(h, -1, sizeof h);
while (m --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
if (spfa()) cout << dist[t] << endl;
else puts("无解");
return 0;
}
```
阅读全文