思路：Dijkstra

本题是一道单源最短路的模板题，不太熟悉图论中如何建图的朋友可以参考这篇文章：笔试ACM模式图论建图模版 - 知乎 (zhihu.com)

最终判断是否能从起点出发到达所有的其他点，如果可以，则输出最远距离，如果不可以，则输出-1。

JavaScript代码

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let n, m;
let ne, h, w, e, idx, dist;
let st;

function add(a, b, c) {
  ne[idx] = h[a];
  e[idx] = b;
  w[idx] = c;
  h[a] = idx++;
}

function dijkstra() {
  const heap = [[0, st]];
  dist[st] = 0;

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, u] = heap.shift();
    if (dist[u] < d) continue;

    for (let i = h[u]; i !== -1; i = ne[i]) {
      const j = e[i];
      if (dist[j] > d + w[i]) {
        dist[j] = d + w[i];
        heap.push([dist[j], j]);
      }
    }
  }

  let res = 0;
  for (let i = 1; i <= n; i++) {
    res = Math.max(res, dist[i]);
  }

  return res === 0x3f3f3f3f ? -1 : res;
}

let lineCount = 0;

rl.on('line', (line) => {
  lineCount++;
  const parts = line.split(' ').map(Number);

  if (lineCount === 1) {
    n = parts[0];
  } else if (lineCount === 2) {
    m = parts[0];
    ne = new Array(n + 1).fill(0);
    h = new Array(n + 1).fill(-1);
    w = new Array(n + 1).fill(0);
    e = new Array(n + 1).fill(0);
    idx = 0;
    dist = new Array(n + 1).fill(0x3f3f3f3f);
  } else if (lineCount > 2 && lineCount <= m + 2) {
    add(parts[0], parts[1], parts[2]);
  } else if (lineCount === m + 3) {
    st = parts[0];
    console.log(dijkstra());
    rl.close();
  }
});

Java代码

import java.util.*;

public class Main {
    static final int N = 510;  // 最大顶点数

    static class Edge {
        int next, to, weight;

        public Edge(int next, int to, int weight) {
            this.next = next;
            this.to = to;
            this.weight = weight;
        }
    }

    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int[] w = new int[N];
    static int[] e = new int[N];
    static int idx;  // 邻接表表示图，ne数组表示链表中下一个节点的索引，h数组表示每个节点的链表头，w数组表示边的权值，e数组表示边的终点，idx表示当前位置

    static int[] dist = new int[N];
    static int st, n, m;  // dist数组表示从源点到各个节点的距离，st表示源点，n表示节点数，m表示边数

    static void add(int a, int b, int c) {
        // 添加一条从a到b的权值为c的边到邻接表
        ne[idx] = h[a];
        e[idx] = b;
        w[idx] = c;
        h[a] = idx++;
    }

    static int dijkstra() {
        // 使用Dijkstra算法计算单源最短路
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(arr -> arr[0]));  // 使用小顶堆作为优先队列，int[]表示整数对，arr[0]表示距离，arr[1]表示节点
        heap.offer(new int[]{0, st});  // 将源点入队，距离为0

        while (!heap.isEmpty()) {
            int[] t = heap.poll();
            int u = t[1], d = t[0];

            for (int i = h[u]; i != -1; i = ne[i]) {
                int j = e[i];

                // 如果通过u到j的距离更短
                if (dist[j] > d + w[i]) {
                    dist[j] = d + w[i];  // 更新距离
                    heap.offer(new int[]{dist[j], j});  // 将新的距离和节点加入优先队列
                }
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, dist[i]);  // 计算最短路径中的最大值
        }

        if (res == 0x3f3f3f3f) return -1;  // 如果最终的最大距离为无穷大，说明有不可达的节点，返回-1
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();  // 读入节点数
        m = scanner.nextInt();  // 读入边数

        Arrays.fill(h, -1);  // 初始化邻接表
        Arrays.fill(dist, 0x3f3f3f3f);  // 初始化距离数组

        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt(), b = scanner.nextInt(), c = scanner.nextInt();
            add(a, b, c);  // 建图，添加有向边
        }

        st = scanner.nextInt();  // 读入源点
        dist[st] = 0;
        System.out.println(dijkstra());  // 输出最短路径的最大距离
    }
}

Python代码

import heapq

N = 510  # 定义一个常量 N，表示数组大小

class Pair:
    def __init__(self, x, y):
        self.x = x  # Pair 的第一个元素
        self.y = y  # Pair 的第二个元素

    def __lt__(self, other):
        return self.x < other.x  # 定义 Pair 对象之间的小于比较，用于堆的排序

ne = [0] * N  # 邻接表的指针数组，记录每个点的第一条边在 e 数组中的位置
h = [-1] * N  # 邻接表的头指针数组，记录每个点的第一条边的位置
w = [0] * N  # 边的权值数组
e = [0] * N  # 边的终点数组
idx = 0  # 边的数量
dist = [0x3f3f3f3f] * N  # 距离数组，用于记录起点到各点的最短距离，初始化为无穷大
st = 0  # 起点
n = 0  # 点的数量
m = 0  # 边的数量

def add(a, b, c):
    global idx  # 使用全局变量
    ne[idx] = h[a]
    e[idx] = b
    w[idx] = c
    h[a] = idx
    idx += 1

def dijkstra():
    global st  # 使用全局变量
    heap = [Pair(0, st)]  # 优先队列，存储 Pair 对象，用于贪心选择最短距离的点
    dist[st] = 0  # 起点到自身的距离为 0
    while heap:
        t = heapq.heappop(heap)  # 弹出堆顶元素，即当前距离起点最近的点
        u, d = t.y, t.x
        i = h[u]
        while i != -1:
            j = e[i]
            if dist[j] > d + w[i]:  # 更新距离数组
                dist[j] = d + w[i]
                heapq.heappush(heap, Pair(dist[j], j))  # 将更新后的距离和点加入堆中
            i = ne[i]
    res = 0
    for i in range(1, n + 1):
        res = max(res, dist[i])  # 找到最长的最短距离，即答案
    if res == 0x3f3f3f3f:
        return -1
    return res

if __name__ == "__main__":
    n = int(input())  # 读入点的数量
    m = int(input())  # 读入边的数量
    h = [-1] * N  # 初始化邻接表的头指针数组
    dist = [0x3f3f3f3f] * N  # 初始化距离数组
    for _ in range(m):
        a, b, c = map(int, input().split())
        add(a, b, c)  # 添加边到邻接表
    st = int(input())  # 读入起点
    print(dijkstra())  # 输出结果

C++代码

#include<bits/stdc++.h>
using namespace std;
int bk[205][205];
int n , m;
void init (){
    memset(bk , -1 , sizeof(bk));
    for (int i = 0 ; i <= n ; i++) bk[i][i] = 0;
}
vector<int> dijstra (int start);
void readEdge (){
    for (int i = 0; i < m; i++) {
        int x , y , z;
        cin >> x >> y >> z;
        if (bk[x][y] == -1)
            bk[x][y] = z;
        else
            bk[x][y] = min(bk[x][y] , z);
    }
}
int main() {
    cin >> n;
    cin >> m;
    init();
    readEdge();
    int start;
    cin >> start;
    vector<int> dis = dijstra(start);
    bool ok = true;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        mx = max(mx , dis[i]);
        if (dis[i] == INT_MAX) {
            ok = false;
            break;
        }
    }
    if (ok) {
        cout << mx << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}
vector<int> dijstra (int start){
    vector<int> dis(n + 1 , INT_MAX);
    vector<bool> vis(n + 1 , false);
    dis[start] = 0;
    for (int i = 1; i <= n; i++) {
        int minn = INT_MAX;
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dis[j] < minn) {
                minn = dis[j];
                u = j;
            }
        }
        if (u == -1) break;
        vis[u] = true;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && bk[u][j] != -1 && dis[u] + bk[u][j] < dis[j]) {
                dis[j] = dis[u] + bk[u][j];
            }
        }
    }
    return dis;
}

题目描述

​ 一个局域网内有很多台电脑，分别标注为 $1$ ~ $N$ 的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用 $t$ 表示. ​ 其中网络内一台电胶被病毒感染，求其感染网络内所有的电脑最少需要多长时间。如果最后有电脑不会感染，则返回 $-1$. ​ 给定一个数组 $times$ 表示一台电脑把相邻电脑感染所用的时间。 如图: $path[i]$ =${i,j,t}$ 表示: 电脑 $i$ -> $j$，电脑 $i$ 上的病毒感染 $j$，需要时间 $t$.

输入描述

第一行输入一个整数 $N$ ，表示局域网内电脑个数 $N$，$1 \le N \le 200$;

第二行输入一个整数 $M$ ,表示有 $M$ 条网络连接；

接下来 $M$行 ,每行输入为 $i , j , t$，代表电脑 $i$ 感染电脑 $j$ 需要时间 $t$。（$1 \le i,j \le N$）

最后一行为病毒所在的电脑编号。

输出描述

输出最少需要多少时间才能感染全部电脑，如果不存在输出 $-1$；

样例1

输入

4
3
2 1 1
2 3 1
3 4 1
2

输出

2

说明

第一个参数：局域网内电脑个数N，1 ≤ N ≤ 200；

第二个参数：总共多少条网络连接

第三个 2 1 1 表示2->1时间为1

第六行：表示病毒最开始所在电脑号2