改变世界的代码

刚看到个挺有意思的贴子，说有段代码“改变世界”：

require"openai"
a = 
b = 2
sum = OpenAI.chat("sum of #{a}+#{b}")
print(sum)

网友们都在调侃，这哪是代码啊，根本跑不起来。

我倒觉得，这段“假代码”反而挺象征性的。以前写代码是让机器算，现在写代码是让AI去“想”。一行逻辑背后，其实是人类和智能的对话。过去程序员靠算法改变世界，以后可能靠一句自然语言实现创造。

算法题：网络延迟时间

昨晚十一点多，我在公司楼下吹风，手机里小李又问我“东哥，那个网络延迟时间到底咋写才稳？”我就…行吧，简单说人话版，别整高深词儿了。

给你若干有向边 times[u, v, w]，表示从 u 发消息到 v 要 w 秒；一共 n 个点，从起点 k 同步一条通知，问多久所有点都能收到；有人永远收不到就返回 -1。你们懂的，像群里我喊“开会”，每个人转发给下家，耗时叠起来。

这事儿本质是“单源最短路”。权重都非负，别犹豫，Dijkstra + 小根堆就完事。用邻接表存图，从 k 出发，堆里每次弹出当前最短的点做“松弛”，把能变短的距离丢回堆。最后取所有点的最短距离里最大那个，就是最慢的那个同学到达时间；有谁没被访问过，说明有人掉线了，直接 -1。

我吃过亏的地方就这仨：第一，节点下标从 1 到 n，别开小数组；第二，访问过的点打标记，避免反复进堆；第三，图不连通别硬求最值，先数数被确认过的点数量，不够 n 直接返回 -1。啊对了，权重大时用 long，LeetCode 这题 int 也够用。

import java.util.*;

publicclassSolution{
publicintnetworkDelayTime(int[][] times, int n, int k){
        List<int[]>[] g = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
for (int[] t : times) g[t[0]].add(newint[]{t[1], t[2]});

int[] dist = newint[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(newint[]{k, 0});

boolean[] vis = newboolean[n + 1];
int visited = 0;

while (!pq.isEmpty()) {
int[] cur = pq.poll();
int u = cur[0], d = cur[1];
if (vis[u]) continue;
            vis[u] = true;
            visited++;
for (int[] e : g[u]) {
int v = e[0], w = e[1];
if (!vis[v] && d + w < dist[v]) {
                    dist[v] = d + w;
                    pq.offer(newint[]{v, dist[v]});
                }
            }
        }
if (visited != n) return -1;
int ans = 0;
for (int i = 1; i <= n; i++) ans = Math.max(ans, dist[i]);
return ans;
    }
}

时间复杂度大概 O(E log V)，空间 O(E + V)。嗯…差不多就这样，我先去泡杯茶，等会谁要是说还超时，八成是把访问标记放错地方了，回去看看堆弹出后再标记就行。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html