两句话

用户名：uq_42709742140

访问量：3393

签　名：

等　　级
排　　名	2787
经　　验	2149
参赛次数	0
文章发表	37
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

Seq2Seq的学习总结
浏览：50

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

3110: 最短路(Spfa)（C++）运用模板/防止时间超限

　　作者: 两句话　　　　发表时间：2024-03-18 18:10:52 浏览：41　|　评论：0　

原题链接：最短路(Spfa)

**本题数据量较大，要注意防止时间超出限制，时间极限的情况下，使用scanf/printf进行输入输出耗时更短**

```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 5e6 + 10;  //N取值应比范围稍大，否则会出现运行错误/出界
typedef pair<int , int> PII;

int h[N] , e[N] , ne[N] , w[N] , idx;
int dist[N];
bool st[N];
int n , m;

void add(int a,int b,int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a] , h[a] = idx++;
 }
int spfa()
{
	memset(dist , 0x3f , sizeof dist);
	dist[1] = 0;

queue<int> q;	//队列存放需要扩展的节点
	q.push(1);
	st[1] = true;	//看当前的点是否在队列当中

while(q.size())
	{//从第一个节点开始扩展
		int t = q.front();
		q.pop();
		st[t] = false;	//扩展后出队
		for(int i = h[t] ; i != -1 ; i = ne[i])
		{
			int j = e[i];
			if(dist[j] > dist[t] + w[i])
			{//更新距离
				dist[j] = dist[t] + w[i];
				if(!st[j])
				{
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	if(dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}

int main()
{
    scanf("%d%d" , &n , &m);  //使用scanf/printf进行输入输出耗时更短
    memset(h , -1 ,sizeof h) ;
    for(int i = 0;i < m;i ++)
    {
        int a , b , c;
        scanf("%d%d%d", &a, &b, &c);
        add(a , b ,c);
        add(b , a ,c);  //无向图
    }
    int t = spfa();
	printf("%d\n" , t);
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

两句话

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

3110: 最短路(Spfa)（C++）运用模板/防止时间超限

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

【偶数求和】（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （用指针求解）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

小O的乘积（C++代码）

快速排序算法1

P1002 （C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

简单的a+b （Java代码）

两句话

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

3110: 最短路(Spfa)（C++）运用模板/防止时间超限

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

【偶数求和】 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （用指针求解）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

小O的乘积 （C++代码）

快速排序算法1

P1002 （C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

简单的a+b （Java代码）

　　评论区

【偶数求和】（C语言代码）

小O的乘积（C++代码）