当前位置：首页 > news >正文

刚备案的域名如何做网站品牌整合营销

news 2025/8/16 11:03:06

刚备案的域名如何做网站,品牌整合营销,安阳信息网官网,客户问你们网站怎么做的算法训练最短路时间限制：1.0s 内存限制：256.0MB问题描述给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号&#xf…

算法训练最短路

时间限制：1.0s 内存限制：256.0MB

问题描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

输入格式

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

输出格式

共n-1行，第i行表示1号点到i+1号点的最短路。

样例输入

3 3
1 2 -1
2 3 -1
3 1 2

样例输出

-1
-2

数据规模与约定

对于10%的数据，n = 2，m = 2。

对于30%的数据，n <= 5，m <= 10。

对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环（在差分约束系统中会得以体现），在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

算法大致思路：

　　s表示源点

　　利用dist[x]表示从源点s到x的最短距离

　　用Q队列来保存需要处理的结点

　　用inQueue[x]保存点x是否在队列中

　　初始化：dist[]数组全部赋值为无穷大，比如INT_MAX（一定要足够大，我一开始就是给小了所以有些数据错了）

　　dist[s] = 0

开始算法：队列+松弛操作

　　读取Q队首元素并出队（记得把inQueue[Q.top()]置为false）

　　对与队首结点相连的所有点v进行松弛操作（如果源点通过队首结点再到结点v的距离比源点直接到v的距离要短，就更新dist[v]，并且如果inQueue[v] == false 即V当前不在队列中，则v入队,当队列Q为空时，判断结束）

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N 200005
 6 #define NN 20005
 7 #define inf 0x3f3f3f3f
 8 #define mem(a,b) memset(a,b,sizeof(a))
 9 using namespace std;
10 queue<int> q;
11 struct Edge{
12     int to;
13     int next;
14     int val;
15 }Edge[N];
16 int M;
17 int dist[NN];
18 int vis[NN];
19 int head[NN];
20 void add(int from,int to,int val){
21     Edge[M].to = to;
22     Edge[M].next = head[from];
23     Edge[M].val = val;
24     head[from] = M++;
25 }
26 
27 void SPFA(int s){
28     dist[s] = 0;
29     q.push(s);
30     vis[s] = 1;
31     while(!q.empty()){
32         int temp = q.front();
33         q.pop();
34         for(int i=head[temp];i!=-1;i=Edge[i].next){
35             int node = Edge[i].to;
36             if(dist[node]>dist[temp]+Edge[i].val){
37                 dist[node] = dist[temp]+Edge[i].val;
38                 if(!vis[node]){
39                     q.push(node);
40                     vis[node] = 1;
41                 }
42             }
43         }
44         vis[temp] = 0;
45     }
46 }
47 
48 int n,m;
49 int main(){
50     std::ios::sync_with_stdio(false);
51     std::cin.tie(0);
52     mem(head,-1);
53     mem(vis,0);
54     mem(dist,inf);
55     cin>>n>>m;
56     for(int i=1;i<=m;i++){
57         int to,from,val;
58         cin>>from>>to>>val;
59         add(from,to,val);
60     }
61     SPFA(1);
62     for(int i=2;i<=n;i++){
63         cout<<dist[i]<<endl;
64     }
65     return 0;
66 }