题解 | #分布式集群消息传递#

解题思路

这是一个基于Dijkstra算法的最短路径问题：

1. 将服务节点之间的消息传递时间构建为有向图
2. 使用Dijkstra算法计算从起始节点 到所有其他节点的最短路径
3. 找出所有最短路径中的最大值，即为所需的最小时间
4. 如果存在无法到达的节点（距离为 ），则返回-1

关键点：

• 需要正确处理输入格式 [[s,d,t],...] 的解析
• 对于重复边，保留时间最短的边
• 注意处理节点不可达的情况

代码

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 104;
const int INF = 0x3fffffff;

int G[MAXN][MAXN];  // 邻接矩阵
int vis[MAXN];      // 访问标记
int d[MAXN];        // 距离数组
int n, k;           // n为节点数，k为起始节点

void dijkstra(int s) {
    d[s] = 0;
    for(int i = 0; i < n; i++) {
        // 找到当前最短距离的节点
        int u = -1, mind = INF;
        for(int j = 1; j <= n; j++) {
            if(!vis[j] && mind > d[j]) {
                mind = d[j];
                u = j;
            }
        }
        
        if(u == -1) return;
        vis[u] = 1;
        
        // 更新相邻节点的距离
        for(int v = 1; v <= n; v++) {
            if(!vis[v] && G[u][v] != INF && d[v] > d[u] + G[u][v]) {
                d[v] = d[u] + G[u][v];
            }
        }
    }
}

int main() {
    // 初始化图
    for(int i = 0; i < MAXN; i++) {
        for(int j = 0; j < MAXN; j++) {
            G[i][j] = (i == j) ? 0 : INF;
        }
    }
    
    // 读入边信息
    char c = getchar();
    while(c != ']') {
        int u, v, t;
        scanf("[%d,%d,%d]", &u, &v, &t);
        if(u != v && t < G[u][v]) {
            G[u][v] = t;
        }
        c = getchar();
    }
    
    // 读入节点数和起始节点
    scanf("%d%d", &n, &k);
    
    // 初始化访问数组和距离数组
    for(int i = 1; i <= n; i++) {
        vis[i] = 0;
        d[i] = INF;
    }
    
    // 执行Dijkstra算法
    dijkstra(k);
    
    // 找出最大距离
    int maxTime = 0;
    for(int i = 1; i <= n; i++) {
        if(d[i] == INF) {
            printf("-1\n");
            return 0;
        }
        maxTime = max(maxTime, d[i]);
    }
    
    printf("%d\n", maxTime);
    return 0;
}

import java.util.*;

public class Main {
    static final int MAXN = 104;
    static final int INF = 0x3fffffff;
    static int[][] G = new int[MAXN][MAXN];
    static int[] vis = new int[MAXN];
    static int[] d = new int[MAXN];
    static int n, k;
    
    static void dijkstra(int s) {
        d[s] = 0;
        for(int i = 0; i < n; i++) {
            int u = -1, mind = INF;
            for(int j = 1; j <= n; j++) {
                if(vis[j] == 0 && mind > d[j]) {
                    mind = d[j];
                    u = j;
                }
            }
            
            if(u == -1) return;
            vis[u] = 1;
            
            for(int v = 1; v <= n; v++) {
                if(vis[v] == 0 && G[u][v] != INF && d[v] > d[u] + G[u][v]) {
                    d[v] = d[u] + G[u][v];
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        
        // 初始化图
        for(int i = 0; i < MAXN; i++) {
            for(int j = 0; j < MAXN; j++) {
                G[i][j] = (i == j) ? 0 : INF;
            }
        }
        
        // 解析输入
        input = input.substring(1, input.length()-1);
        String[] edges = input.split("\\],\\[");
        for(String edge : edges) {
            edge = edge.replaceAll("\\[|\\]", "");
            String[] nums = edge.split(",");
            int u = Integer.parseInt(nums[0]);
            int v = Integer.parseInt(nums[1]);
            int t = Integer.parseInt(nums[2]);
            if(u != v && t < G[u][v]) {
                G[u][v] = t;
            }
        }
        
        n = sc.nextInt();
        k = sc.nextInt();
        
        // 初始化访问数组和距离数组
        for(int i = 1; i <= n; i++) {
            vis[i] = 0;
            d[i] = INF;
        }
        
        dijkstra(k);
        
        int maxTime = 0;
        for(int i = 1; i <= n; i++) {
            if(d[i] == INF) {
                System.out.println(-1);
                return;
            }
            maxTime = Math.max(maxTime, d[i]);
        }
        
        System.out.println(maxTime);
    }
}

from sys import stdin
import ast

INF = float('inf')
MAXN = 104

def dijkstra(G, n, s):
    d = [INF] * (n + 1)
    vis = [0] * (n + 1)
    d[s] = 0
    
    for i in range(n):
        u = -1
        mind = INF
        for j in range(1, n + 1):
            if not vis[j] and mind > d[j]:
                mind = d[j]
                u = j
        
        if u == -1:
            break
            
        vis[u] = 1
        for v in range(1, n + 1):
            if not vis[v] and G[u][v] != INF and d[v] > d[u] + G[u][v]:
                d[v] = d[u] + G[u][v]
    
    return d

# 读入并解析输入
edges = ast.literal_eval(input())
n = int(input())
k = int(input())

# 初始化图
G = [[INF] * MAXN for _ in range(MAXN)]
for i in range(MAXN):
    G[i][i] = 0

# 构建图
for u, v, t in edges:
    if u != v and t < G[u][v]:
        G[u][v] = t

# 执行Dijkstra算法
d = dijkstra(G, n, k)

# 计算结果
max_time = 0
for i in range(1, n + 1):
    if d[i] == INF:
        print(-1)
        exit()
    max_time = max(max_time, d[i])

print(max_time)

算法及复杂度

• 算法：Dijkstra最短路径算法
• 时间复杂度： - 标准Dijkstra算法的复杂度
• 空间复杂度： - 邻接矩阵存储图的空间复杂度