• 欢迎光临~

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

开发技术 开发技术 2022-08-04 次浏览

1.问题描述

有 N 个网络节点,标记为 1 到 N。

给定一个列表 times,表示信号经过有向边的传递时间。 times[i] = (u, v, w),其中 u 是源节点,v 是目标节点, w 是一个信号从源节点传递到目标节点的时间。

现在,我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1。

 

示例:

times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2

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

输入:

4 3 2

2 1 1

2 3 1

3 4 1

输出:2

 

可使用以下main函数:

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=Solution().networkDelayTime(times,N,K);

    cout<<res<<endl;

}

 

 

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 <iostream>
#include <queue>
#include <cstdlib>
#include <cstring>
#include<map>
#include<vector>
#include<algorithm>
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;

}

 

程序员灯塔
转载请注明原文链接:力扣练习——50 网络延迟时间
喜欢 (0)