memset(dist,-1,sizeof(dist))
时间: 2024-05-24 19:11:08 浏览: 7
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.
相关问题
memset(dist,0x3f,sizeof dist);这句话是什么意思
这句话的意思是将数组dist中的所有元素初始化为0x3f,这是因为0x3f在二进制中表示为11111111,意味着最大值。所以这句话的作用就是将dist数组中的所有元素初始化为一个最大值,以便在后续的算法中能够区分出尚未更新的节点。
算法思路分析:#include <bits/stdc++.h> using namespace std; const int N = 253; int a[N][N], n, m, now, pre[N]; long long dist[N], shortest, t; bool vist[N]; int main(){ int u, v, e; memset(a, -1, sizeof(a)); scanf("%d %d", &n, &m); //n个结点,m条边 for (int i = 1; i <= m; ++i) { scanf("%d %d %d", &u, &v, &e); //节点u和节点v之间有一条长度为e的无向边 a[u][v] = a[v][u] = e; } memset(dist, 127, sizeof(long long) * (n + 1)); dist[1] = 0; for (int i = 1; i <= n; ++i) { now = -1; for (int j = 1; j <= n; ++j) if (!vist[j] && ((dist[j] < dist[now]) || (now == -1))) now = j; if (now == -1) break; for (int j = 1; j <= n; ++j) if (!vist[j] && a[now][j] != -1 && (t = (dist[now] + a[now][j])) < dist[j]) { dist[j] = t; pre[j] = now; } vist[now] = true; } shortest = dist[n]; int tmp = n; long long ans = shortest; while (tmp != 1) { a[pre[tmp]][tmp] <<= 1; a[tmp][pre[tmp]] <<= 1; memset(dist, 127, sizeof(long long) * (n + 1)); memset(vist, 0, sizeof(bool) * (n + 1)); dist[1] = 0; for (int i = 1; i <= n; ++i) { now = -1; for (int j = 1; j <= n; ++j) if (!vist[j] && ((dist[j] < dist[now]) || (now == -1))) now = j; if (now == -1) break; for (int j = 1; j <= n; ++j) if (!vist[j] && a[now][j] != -1 && (t = (dist[now] + a[now][j])) < dist[j]) dist[j] = t; vist[now] = true; } ans = max(ans, dist[n]); a[pre[tmp]][tmp] >>= 1; a[tmp][pre[tmp]] >>= 1; tmp = pre[tmp]; } printf("%lld\n", ans - shortest); return 0; }
这段代码实现了一种求解有向无环图中最短路径问题的方法,叫做"起点可撤销"算法,也称为"反悔算法"或"替身算法"。
具体思路如下:
1. 使用Dijkstra算法求出从起点到终点的最短路径。
2. 从终点向起点遍历最短路径,对于每一条边,将其边权乘以2,并重新计算最短路径。
3. 对于每次重新计算得到的最短路径,记录其中的最大值。
4. 将边权还原回原来的值,继续遍历最短路径,直到遍历完整条路径。
5. 最后输出最大的重新计算得到的最短路径减去原来的最短路径。
代码中使用了一个名为pre的数组来记录最短路径上每个节点的前驱节点,使用了一个名为dist的数组来记录每个节点到起点的最短距离,使用了一个名为a的二维数组来存储图的邻接矩阵表示,-1表示两个节点之间没有边。
需要注意的是,代码中使用了memset函数来初始化数组,将数组中的每个元素都赋为-1或者一个足够大的数,这是为计算最短路径做准备的。
此外,在计算最短路径的过程中,使用了一个名为vist的数组来记录每个节点是否已经被访问过,使用了一个名为now的变量来记录当前遍历到的节点。
最后,输出答案即可。
总的来说,这种算法思路比较巧妙,但需要注意实现细节。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)