力扣练习——50 网络延迟时间

int N,M,K;

vector > times;

cin>>N>>M>>K;

int u,v,w;

for(int i=0; i>u>>v>>w;

    vector time;

    time.push_back(u);

    time.push_back(v);

    time.push_back(w);

    times.push_back(time);

}

int res=Solution().networkDelayTime(times,N,K);

cout<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29

}
2.输入说明
首先输入网络节点个数N，传递时间列表 times的长度M，起始节点K

然后输入M行，每行三个整数(u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

N 的范围在 [1, 100] 之间。

K 的范围在 [1, N] 之间。

times 的长度M在 [1, 6000] 之间。

所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。
3.输出说明
输出一个整数，表示结果。
4.范例
输入
4 3 2
2 1 1
2 3 1
3 4 1
输出
2
5.代码

#include 
#include 
#include 
#include 
#include
#include
#include
using namespace std;

int networkDelayTime(vector<vector<int> > times,int N,int K) {

	//带权有向图问题，连通性判断，遍历时间计算【遍历到所有节点最长需要多少时间】
	//使用Dijkstra算法 用来解决单源最短路问题
	//思想：贪心
	/*设置集合S存放已被访问的顶点，然后执行n次下面的两个步骤(n为顶点个数)
		1）每次从集合V - S中选择与起点v0的最短距离最小的一个顶点(记为u)，访问并加入集合S。
		2）之后，令顶点u为中间点，优化起点v0与所有从u能到达的顶点v之间的最短距离。*/

	const int INF = INT_MAX/2;//到不了的节点初始距离都为无穷大
	//遍历图，更新（u，v）之间的距离  times中的点表示为(u,v,w)u为起点，v为终点，w为权重
	//创建二维数组dist[u][v]
	vector<vector<int> >g(N, vector<int>(N, INF));
	for (auto t : times)
	{
		int u = t[0]-1;//起点,   为了方便，存储时将原来的编号 1-N 缩小为 0-N-1
		int v = t[1]-1;//终点
		int w = t[2];//距离【权重】
		g[u][v] = w;
	}
	//记录源点v0到所有其他顶点的距离 ,这里v0是K-1
	vector<int>dist(N, INF);
	dist[K-1] = 0;
	//标记该节点是否已经加入到S中
	vector<int>visited(N);
	for (int i = 0; i < N; i++)
	{
		int x = -1;
		for (int y = 0; y < N; y++)
		{
			//注意这里是选择未被归入集合S的节点中的距离v0最近的那个点
			//注意这里的u==-1不可以省略    len[j]是指编号为K-1的节点【也就是V0点，源点】到编号为j的节点【原图中的j+1点】的距离
			if (visited[y] == false && ( x == -1 || dist[y] < dist[x]))//从所有未被选择的节点中选择距离最近的节点，加入S中，并更新v0到其余剩下节点的距离的最小值
			{
				x = y;//找到距离源点最短距离的点，归入到集合S中
			}
		}
		visited[x] = true;//已经归入S中，添加标记
		//更新源点到其他点的距离
		for (int y = 0; y < N; y++)
		{
			dist[y] = min(dist[y], dist[x] + g[x][y]);//判断 将新加入的节点u作为中间点，会不会使源点到其他点的距离变短？
		}
	}

	sort(dist.begin(), dist.end());
	int ans = dist[N - 1];//返回最大值

	return ans == INF ? -1 : ans;//如果存在到不了的点，那就输出-1


	//后记：有好几个地方需要注意
	//1.要防止溢出的问题，dist[x]+g[x][y]得到的数字可能会超出int型的范围，因此必须把INF设置成INT_MAX/2
	//2.最后输出的地方，不要写错等号 ，是双等号！！否则是赋值操作
}

int main()

{

	int N, M, K;

	vector<vector<int> > times;

	cin >> N >> M >> K;

	int u, v, w;

	for (int i = 0; i < M; i++)

	{

		cin >> u >> v >> w;

		vector<int> time;

		time.push_back(u);

		time.push_back(v);

		time.push_back(w);

		times.push_back(time);

	}

	int res = networkDelayTime(times, N, K);

	cout << res << endl;

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102