HPCGames 题解 D E 题

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

背景

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

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

任务描述

本题是一个经典的单源最短路 (Single Source Shortest Path, SSSP) 问题。给定一个包含 $n$ 个节点和 $m$ 条边的有向图 $G=(V,E)$，边的权重 $w\leq0$。你需要计算从源点 $s=0$ 到图中所有其他节点 $v\in V$ 的最短路径长度。

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

输入输出

本题中输入输出函数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$ 的最短路径长度。如果节点不可达，输出 1e18。保证输出不会溢出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

评测

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

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

对于所有测试点，所有图都是随机图，dis已初始化，具体详见main.cpp。

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

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

可以访问hpcgames ↗查找相关附件下载。