问题与解答

问题描述

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

给定一个二维数组times[M][3]，表示信号经过有向边的传递时间。times[i][3] = {u, v, w}, 其中u是源节点，v是目标节点，w是一个信号从源节点传递到目标节点的时间，即二维数组中的一行表示一条带权有向边。

现在，我们向当前的节点K 发送一个信号。最少需要多长时间才能使所有节点都收到信号？如果不能使所有节点收到信号，返回-1。

注意：

1、 M的范围在[1,50]之间

2、 N的范围在[1, 20] 之间。

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

4、所有的边times[i][3] =（u, v, w）都有1 <= u, v <= N 且 1 <= w <= 50。

问题输入

多行输入数据，第1行为3个正整数，分别是M，N，K。接下来有M行，每行有3个正整数，分别是u, v, w。

**问题输出 **

输出一个数，表示需要多久才能使所有节点都收到信号。如果不能使所有节点收到信号，返回-1

输入样例

3 4 2

2 1 1

2 3 1

3 4 1

输出样例

2

//网络时延

//最短路径问题: Dijstra

#include<stdio.h>

#include<algorithm>

using namespace std;

#define MaxN 100  //最大顶点数

#define INF 10000

int N;  //顶点数

int G[MaxN][MaxN];  //邻接矩阵保存图G

int d[MaxN];  //d[u] = num：顶点u到起点的距离为num,初始化为INF

bool Vis[MaxN] = {false};  //Vis[i] == true：顶点i已被访问

int Dijstra(int s);  //Dijstra算法，输入起点s

int main(){

    int M,K,Min_Length;

    int i,j;

    int u,v,w;

    fill(G[0],G[0]+MaxN*MaxN,0);  //初始化图G

    scanf("%d%d%d",&M,&N,&K);   //读入图G的边

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

        scanf("%d%d%d",&u,&v,&w);

        G[u-1][v-1] = w;

    }

    Min_Length = Dijstra(K-1);  //调用Dijstra算法

    printf("%d", Min_Length);   //打印最短路径

}

int Dijstra(int s){

    fill(d,d+N,INF);

    d[s] = 0;

    int i,u,v,Min;

    for(i = 0; i < N; i++){  //循环N次

        u = -1, Min = INF;

        for(v = 0; v < N; v++){  //未访问 && 距离起点最近的点

            if(Vis[v] == false && d[v] < Min){

                u = v;

                Min = d[v];

            }

        }

        if(u == -1) return -1;   //不连通，返回-1

        Vis[u] = true;

        for(v = 0; v < N; v++){  //以u为中介点优化u未被访问的邻接点

            if(Vis[v] == false && G[u][v] != 0 && d[u]+G[u][v] < d[v])

                d[v] = d[u] + G[u][v];

        }

    }

    int Min_Length = -1;  //返回结果

    for(u = 0; u < N; u++){

        if(d[u] > Min_Length)

            Min_Length = d[u];

    }

    return Min_Length;

}

题后反思

用fill初始化数组

一维：fill(d,d+N,INF);
二维：fill(G[0], G[0]+MaxN * MaxN, 0);

编号问题

编号从1开始计时，G的顶点编号以及传入Dijstra的起点K的编号都 == 读入编号 - 1

巴特西

<数据结构>XDOJ326.网络延时

问题与解答

题后反思

用fill初始化数组

编号问题

最新文章

热门文章