526互联

743. 网络延迟时间

发布时间 2024-01-09 22:04:51作者: 不是孩子了

vector一/二维数组的定义
C++求最值
迪杰斯特拉算法

//单源最短路径
//BFS单源最短路径适用于无权图
//对于带权图，可以用迪杰斯特拉算法或者Floyd算法求解

//网络延迟时间
#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
#include<queue>
#include<algorithm>
using namespace std;

//Dijkstra算法
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int inf = INT_MAX / 2;

        //定义二位数组存储邻接矩阵
        vector<vector<int>> g(n, vector<int>(n, inf)); //第一个n是一共n行，第二个vector<int>(n,
                                     //inf)中的n是n列，inf是[i,j]初始化为inf
        //初始化邻接矩阵
        for (auto &t : times) {
            int i = t[0]-1, j = t[1]-1;
            g[i][j] = t[2];
        }

        vector<int> dist(n, inf); //距离数组
        dist[k - 1] = 0;          //顶点k是起始顶点

        vector<bool> used(n, false); //该顶点是否被初始化

        for (int i = 0; i < n; i++) {

            //寻找最短路径
            int x = -1;
            for (int j = 0; j < n; j++) {
                if (!used[j] && (x==-1 || dist[j] < dist[x])) {
                    x = j;
                }
            }

            //更新x到其他点的距离
            used[x] = true;

            for (int j = 0; j < n; j++) {
                dist[j] = min(dist[j], dist[x] + g[x][j]);
            }
        }

        //寻找最大值，即延迟时间最长
        int result = *max_element(dist.begin(), dist.end());
        return result == inf ? -1 : result;
    }

int main()
{
    vector<vector<int>> times;

    int a[3] = {1, 2, 3};
    vector<int> v(a, a+3);
    times.push_back(v);

    int result = networkDelayTime(times, 2, 1);

    return 0;
}