D. Hyperlane Hopper¶

分数：150 分

“在那无穷的星辰大海中，最近的路往往不是直线，而是过路费最少的那条。” —— 银河联邦导航员手册，第 42 章

背景¶

公元 30777 年，人类文明实现了银河系的互通，连接这些星系的是一种被称为 "Hyperlane" 的古老网络。每条航道连接两个星系，由于引力波动、空间碎片以及道路维护费不同，每条航道的通行代价都是不一样的，且均为非负整数。

你作为银河速运的首席算法架构师，面临着一个严峻的问题：随着双十一的临近，由于订单量暴涨，从人类文明早期传承下来的单线程导航核心（基于古老的 Dijkstra 算法）已经无法在客户失去耐心前规划出最短路径。因为系统还运行在 30000 年前构建的服务器上（没有人敢动），无法使用高效的量子计算资源。好在你从地球南极挖出了 github 保存的 16 核 CPU 服务器，准备将导航系统升级为多线程版本，以提升路径规划的效率。至于其他部分，那就期待后人的智慧吧。

任务描述¶

本题是一个经典的单源最短路 (Single Source Shortest Path, SSSP) 问题。给定一个包含 $n$ 个节点和 $m$ 条边的有向图 $G=(V, E)$，边的权重 $w \ge 0$。

你可以使用任何算法来解决这个问题，只要最终结果正确即可。建图部分也可以优化。

输入输出¶

本题中输入输出函数 main.cpp已经为你实现，它会调用sssp.cpp中的calculate函数，函数原型如下。不过我们仍然在此处说明输入输出格式以便参考。你可以在handout目录下找到main.cpp 的实现。

void calculate(uint32_t n, uint32_t m, uint32_t *edges, uint64_t *dis)

输入¶

程序接受三个参数，n、m和seed，分别表示节点数、边数和随机数种子。程序会根据这些参数生成一个有向图。

输出¶

程序输出一个二进制文件，文件名是 dis.bin，其中包括 $n$ 个 64 位无符号整数，第 $i$ 个整数表示从源点 $0$ 到节点 $i$ 的最短路径长度。如果节点不可达，输出0xFFFFFFFFFFFFFFFF。保证输出不会溢出uint64_t 的范围。

运行环境、编译与测试¶

本题将在 Intel Xeon Platinum 8358 CPU 的 16 核心环境下运行。

评测容器镜像：cr.hpc.lcpu.dev/hpcgame/base:latest，基础发行版为Rocky Linux 10.1。编译命令如下。我们在 handout 里提供了一个Makefile，你也可以直接使用下面的命令编译：

g++ -O3 -std=c++20 -flto -march=native -fopenmp -pthread -o sssp main.cpp sssp.cpp

我们会这样运行：

export OMP_NUM_THREADS=16
export OMP_PLACES=cores
export OMP_PROC_BIND=close
./sssp n m seed

评测¶

所有结果必须正确，否则不得分。

数据可能存在重边和自环。数据保证所有点可达。

对于所有测试点，边长随机分布在 $[1, 10^7]$。所有图都是随机图，dis已初始化，具体详见main.cpp 。

每个测试点得到正确结果获得基本分数，性能分数与运行时间倒数成正比。

final_score = correct? base_score + perf_score * min(goal / time, 1): 0

附件¶

• handout-sssp