跳转至

# Python 速成

## 关于 Python

Python 是一门已在世界上广泛使用的解释型语言．它提供了高效的高级数据结构，还能简单有效地面向对象编程，也可以在算法竞赛．

### Python 的优点

- Python 是一门 解释型 语言：Python 不需要编译和链接，可以在一定程度上减少操作步骤．
- Python 是一门 交互式 语言：Python 解释器实现了交互式操作，可以直接在终端输入并执行指令．
- Python 易学易用：Python 提供了大量的数据结构，也支持开发大型程序．
- Python 兼容性强：Python 同时支持 Windows、macOS 和 Unix 操作系统．
- Python 实用性强：从简单的输入输出到科学计算甚至于大型 WEB 应用，都可以写出适合的 Python 程序．
- Python 程序简洁、易读：Python 代码通常比实现同种功能的其他语言的代码短．
- Python 支持拓展：Python 会开发 C 语言程序（即 CPython），支持把 Python 解释器和用 C 语言开发的应用链接，用 Python 扩展和控制该应用．

### 学习 Python 的注意事项

- 目前主要使用的 Python 版本是 Python 3.7 及以上的版本，Python 2 和 Python 3.6 及以前的 Python 3 已经 不被支持，但仍被一些老旧系统与代码所使用．本文将 介绍较新版本的 Python．如果遇到 Python 2 代码，可以尝试 `2to3` 程序将 Python 2 代码转换为 Python 3 代码．
- Python 的设计理念和语法结构 与一些其他语言的差异较大，隐藏了许多底层细节，所以呈现出实用而优雅的风格．
- Python 是高度动态的解释型语言，因此其 程序运行速度相对较慢，尤其在使用其内置的 `for` 循环语句时．在使用 Python 时，应尽量使用 `filter`、`map` 等内置函数，或使用 列表生成 语法的手段来提高程序性能．

## 环境搭建

参见 Python 3．或者：

- Windows：也可以在 Microsoft Store 中免费而快捷地获取 Python．

- macOS/Linux：通常情况下，大部分的 Linux 发行版中已经自带了 Python．如果只打算学习 Python 语法，并无其它开发需求，不必另外安装 Python．

  注意

  在一些默认安装（指使用软件包管理器安装）Python 的系统（如 Unix 系统）中，应在终端中运行 `python3` 打开 Python 3 解释器．2

此外，也可以通过 venv、conda、Nix 等工具管理 Python 工具链和 Python 软件包，创建隔离的虚拟环境，避免出现依赖问题．

作为一种解释型语言，Python 的执行方式和 C++ 有所不同，这种差异在使用 IDE 编程时往往得不到体现，因此这里需要强调一下运行程序的不同方式．

当在命令行中键入 `python3` 或刚刚打开 IDLE 时，你实际进入了一种交互式的编程环境，也称「REPL」（「读取 - 求值 - 输出」循环），初学者可以在这里输入语句并立即看到结果，这让验证一些语法变得极为容易，我们也将在后文中大量使用这种形式．

但若要编写完整的程序，你最好还是新建一个文本文件（通常后缀为 `.py`），然后在命令行中执行 `python3 filename.py`，就能够运行代码看到结果了．

### 一些平台提供的 Python 版本

系统名/版本 | python 版本
--- | ---
Noi Linux 2.0 | 3.8.0, Include requests
Luogu 评测机 | 3.11.5, NumPy 1.25.2
基于 Hydro 的 OJ | 3.8.0+ Include NumPy
Ubuntu 22.04（内置） | 3.10.4
微软商店 | 最新正式版

注意

本表格在本文撰写时（2025/01/15）时有效，建议前往相关平台重新查证．

目前国内关于 源码 的镜像缓存主要是 北京交通大学自由与开源软件镜像站 和 华为开源镜像站，可以到那里尝试下载 Python 安装文件．

## 使用 `pip` 安装第三方库

Python 的生命力很大程度上来自于丰富的第三方库，编写一些实用程序时「调库」是常规操作，`pip` 是首选的安装第三方库的程序．自 Python 3.4 版本起，它被默认包含在 Python 二进制安装程序中．

`pip` 中的第三方库主要存储在 Python 包索引（PyPI） 上，用户也可以指定其它第三方库的托管平台．使用方法可参照 pypi 镜像使用帮助 - 清华大学开源软件镜像站 等使用帮助．你可以在 MirrorZ 上获取更多 PyPI 镜像源．

使用清华大学开源镜像站安装一个包

    1
    pip install -i https://mirrors.tuna.tsinghua.edu.cn/pypi/web/simple <some-package>

## 基本语法

Python 的语法简洁而易懂，也有许多官方和第三方文档与教程．这里仅介绍一些对 OIer 比较实用的语言特性，你可以在 Python 文档 和 Python Wiki 等网页上了解更多关于 Python 的教程．

### 注释

加入注释并不会对代码的运行产生影响，但加入注释可以使代码更加易懂易用．

    1
    2
    3
    4
    5
    6
    7
    # 用 # 字符开头的是单行注释

    """
    跨多行字符串会用三引号
    （即三个单引号或三个双引号）
    包裹，但也通常被用于注释
    """

加入注释代码并不会对代码产生影响．我们鼓励加入注释来使代码更加易懂易用．

### 基本数据类型

#### 一切皆对象

在 Python 中，你无需事先声明变量名及其类型，直接赋值即可创建各种类型的变量：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    >>> x = -3  # 语句结尾不用加分号
    >>> x
    -3
    >>> f = 3.1415926535897932384626; f  # 实在想加分号也可以，这里节省了一行
    3.141592653589793
    >>> s1 = "O"
    >>> s1  # 在 Python 中双引号和单引号的作用相同
    'O'
    >>> b = 'A' == 65  # 'A' 和 65 不是一个数据类型，所以不相等
    >>> b  # True, False 首字母均大写
    False
    >>> True + 1 == 2 and not False != 0  # Python 中的表达式中大多使用单词，但是也支持符号
    True

但这不代表 Python 没有类型的概念，实际上解释器会根据赋值或运算自动推断变量类型，你可以使用内置函数 `type()` 查看这些变量的类型：

    1
    2
    3
    4
    5
    6
    7
    8
    >>> type(x)
    <class 'int'>
    >>> type(f)
    <class 'float'>
    >>> type(s1)  # 请注意，不要给字符串起名为 str，否则 str 对象会被篡改
    <class 'str'>
    >>> type(b)
    <class 'bool'>

内置函数 是什么？

在 C/C++ 中，很多常用函数都分散在不同的头文件中，但 Python 的解释器内置了许多实用且通用的函数，你可以直接使用而无需注意它们的存在，但这也带来了小问题，这些内置函数的名称多为常见单词，你需要注意避免给自己的变量起相同的名字，否则可能会产生奇怪的结果．

正如我们所看到的，Python 内置有整数、浮点数、字符串和布尔类型，可以类比为 C++ 中的 `int`，`float`，`string` 和 `bool`．但有一些明显的不同之处，比如没有 `char` 字符类型，也没有 `double` 类型（但 `float` 其实对应 C 中的双精度），如果需要更精确的浮点运算，可以使用标准库中的 decimal 模块，如果需要用到复数，Python 还内置了 `complex` 类型（而这也意味着最好不要给变量起名为 `complex`）． 可以看到这些类型都以 `class` 开头，而这正是 Python 不同于 C++ 的关键之处，Python 程序中的所有数据都是由对象或对象间关系来表示的，函数是对象，类型本身也是对象：

    1
    2
    3
    4
    5
    6
    >>> type(int)
    <class 'type'>
    >>> type(pow)  # 求幂次的内置函数，后文会介绍
    <class 'builtin_function_or_method'>
    >>> type(type)  # type() 也是内置函数，但有些特殊，感兴趣可自行查阅
    <class 'type'>

你或许会觉得这些概念一时难以理解且没有用处，所以我们暂时不再深入，在后文的示例中你或许能慢慢体会到，Python 的对象提供了强大的方法，我们在编程时应当优先考虑围绕对象而不是过程进行操作，这会让我们的代码显得更加紧凑明晰．

#### 数字运算

有人说，你可以把你系统里装的 Python 当作一个多用计算器，这是事实．
在交互模式下，你可以在提示符 `>>>` 后面输入一个表达式，就像其他大部分语言（如 C++）一样使用运算符 `+`、`-`、`*`、`/`、`%` 来对数字进行运算，也可以使用 `()` 来进行符合结合律的分组，读者可以自行试验，在这里我们仅展示与 C++ 差异较大的部分：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    >>> 5.0 * 6  # 浮点数的运算结果是浮点数
    30.0
    >>> 15 / 3  # 与 C/C++ 不同，除法永远返回浮点 float 类型
    5.0
    >>> 5 / 100000  # 位数太多，结果显示成科学计数法形式
    5e-05
    >>> 5 // 3 # 使用整数除法（地板除）则会向下取整，输出整数类型
    1
    >>> -5 // 3 # 符合向下取整原则，注意这与 C/C++ 不同
    -2
    >>> 5 % 3 # 取模
    2
    >>> -5 % 3 # 负数取模结果一定是非负数，这点也与 C/C++ 不同，不过都满足 (a//b)*b+(a%b)==a
    1
    >>> x = abs(-1e4)  # 求绝对值的内置函数
    >>> x += 1  # 没有自增/自减运算符
    >>> x  # 科学计数法默认为 float
    10001.0

在上面的实践中可以发现，除法运算（`/`）永远返回浮点类型（在 Python 2 中返回整数）．如果你想要整数或向下取整的结果的话，可以使用整数除法（`//`）．同样的，你也可以像 C++ 中一样，使用模（`%`）来计算余数，科学计数法的形式也相同．

特别地，Python 用 `**` 即可进行幂运算，还通过内置的 `pow(a, b, mod)` 提供了 快速幂 的高效实现．

    1
    2
    3
    4
    5
    6
    7
    8
    9
    >>> 3 ** 4 # 幂运算
    81
    >>> 2 ** 512
    13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
    >>> pow(2, 512, int(1e4)) # 即 2**512 % 10000 的快速实现, 1e4 是 float 所以要转 int
    4096
    >>> 2048 ** 2048 # 在IDLE里试试大整数？
    >>> 0.1 + 0.1 + 0.1 - 0.3 == 0.  # 和 C/C++ 一样需要注意浮点数不能直接判相等
    False

#### 数据类型判断

对于一个变量，可以使用 `type(object)` 返回变量的类型，例如 `type(8)` 和 `type('a')` 的值分别为 `<class 'int'>` 和 `<class 'str'>`．

#### 基本输入输出

Python 中的输入输出主要通过内置函数 `input()` 和 `print()` 完成，`print()` 的用法十分符合直觉：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    >>> a = [1,2,3]; print(a[-1])  # 打印时默认末尾换行
    3
    >>> print(ans[0], ans[1])  # 可以输出任意多个变量，默认以空格间隔
    1 2
    >>> print(a[0], a[1], end='')  # 令 end='', 使末尾不换行
    1 2>>>
    >>> print(a[0], a[1], sep=', ')  # 令 sep=', '，改变间隔样式
    1, 2
    >>> print(str(a[0]) + ', ' + str(a[1]))  # 输出同上，但是手动拼接成一整个字符串

`input()` 函数的行为接近 C++ 中的 `getline()`，即将一整行作为字符串读入，且末尾没有换行符．

    1
    2
    3
    >>> s = input('请输入一串数字: '); s  # 自己调试时可以向 input() 传入字符串作为提示
    请输入一串数字: 1 2 3 4 5 6
    '1 2 3 4 5 6'

#### 字符串

Python 3 提供了强大的基于 Unicode 的字符串类型，使用起来和 C++ 中的 `string` 类似，一些概念如转义字符也都相通，除了加号拼接和索引访问，还额外支持数乘 `*` 重复字符串，和 `in` 操作符．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    >>> s1 = "O"  # 单引号和双引号都能包起字符串，有时可节省转义字符
    >>> s1 += 'I-Wiki'  # 为和 C++ 同步建议使用双引号
    >>> 'OI' in s1  # 检测子串很方便
    True
    >>> len(s1)  # 类似 C++ 的 s.length()，但更通用
    7
    >>> s2 = """ 感谢你的阅读
    ... 欢迎参与贡献!
    """   # 使用三重引号的字符串可以跨越多行
    >>> s1 + s2
    'OI-Wiki 感谢你的阅读\n欢迎参与贡献!'
    >>> print(s1 + s2)  # 这里使用了 print() 函数打印字符串
    OI-Wiki 感谢你的阅读
    欢迎参与贡献!
    >>> s2[2] * 2 + s2[3] + s2[-1]  # 负数索引从右开始计数，加上 len(s)，相当于模 n 的剩余类环
    '谢谢你!'
    >>> s1[0] = 'o'  # str 是不可变类型，不能原地修改，其实 += 也是创建了新的对象
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: 'str' object does not support item assignment

Python 支持多种复合数据类型，可将不同值组合在一起．最常用的 `list`，类型是用方括号标注、逗号分隔的一组值．例如，`[1, 2, 3]` 和 `['a','b','c']` 都是列表．

除了索引，字符串还支持切片，它的设计非常精妙，格式为 `s[左闭索引:右开索引:步长]`：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    >>> s = 'OI-Wiki 感谢你的阅读\n欢迎参与贡献!'
    >>> s[:8]  # 省略左闭索引则从头开始
    'OI-Wiki '
    >>> s[8:14]  # 左闭右开设计的妙处，长度为 14-8=6，还和上一个字符串无缝衔接
    '感谢你的阅读'
    >>> s[-4:]  # 省略右开索引则直到结尾
    '与贡献!'
    >>> s[8:14:2]  # 步长为2
    '感你阅'
    >>> s[::-1]  # 步长为 -1 时，获得了反转的字符串
    '!献贡与参迎欢\n读阅的你谢感 ikiW-IO'
    >>> s  # 但原来的字符串并未改变
    'OI-Wiki 感谢你的阅读\n欢迎参与贡献!'

在最新的 Python 3 版本中，字符串是以 Unicode 编码的，也就是说，Python 的字符串支持多语言．1在 Python 中，可以对一个 Unicode 字符使用内置函数 `ord()` 将其转换为对应的 Unicode 编码，逆向的转换使用内置函数 `chr()`．C/C++ 中 `char` 类型也可以和 对应的 ASCII 码互转．

如果想把数字转换成对应的字符串，可以使用内置函数 `str()`，反之可以使用 `int()` 和 `float()`，你可以类比为 C/C++ 中的强制类型转换，但括号不是加在类型上而是作为函数的一部分括住参数．

Python 的字符串类型提供了许多强大的方法，包括计算某字符的索引与出现次数，转换大小写等等，这里就不一一列举，强烈建议查看 官方文档 熟悉常用方法，遇到字符串操作应当首先考虑使用这些方法而非自力更生．

### 创建数组

从 C++ 转过来的同学可能很迷惑怎么在 Python 中创建数组，这里就介绍在 Python 开「数组」的语法，需要强调我们介绍的其实是几种 序列类型，和 C 的数组有着本质区别，而更接近 C++ 中的 `vector`．

#### 使用 `list`

列表（`list`）大概是 Python 中最常用也最强大的序列类型，列表中可以存放任意类型的元素，包括嵌套的列表，这符合数据结构中「广义表」的定义．请注意不要将其与 C++ STL 中的双向链表 `list` 混淆，故本文将使用「列表」而非 `list` 以免造成误解．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    >>> []  # 创建空列表，注意列表使用方括号
    []
    >>> nums = [0, 1, 2, 3, 5, 8, 13]; nums  # 初始化列表，注意整个列表可以直接打印
    [0, 1, 2, 3, 5, 8, 13]
    >>> nums[0] = 1; nums  # 支持索引访问，支持修改元素
    [1, 1, 2, 3, 5, 8, 13]
    >>> nums.append(nums[-2]+nums[-1]); nums  # append() 同 vector 的 push_back()，也都没有返回值
    [1, 1, 2, 3, 5, 8, 13, 21]
    >>> nums.pop()  # 弹出并返回末尾元素，可以当栈使用；其实还可指定位置，默认是末尾
    21
    >>> nums.insert(0, 1); nums  # 同 vector 的 insert(position, val)
    [1, 1, 1, 2, 3, 5, 8, 13]
    >>> nums.remove(1); nums  # 按值移除元素（只删第一个出现的），若不存在则抛出错误
    [1, 1, 2, 3, 5, 8, 13]
    >>> len(nums)  # 求列表长度，类似 vector 的 size()，但 len() 是内置函数
    7
    >>> nums.reverse(); nums  # 原地逆置
    [13, 8, 5, 3, 2, 1, 1]
    >>> sorted(nums)  # 获得排序后的列表
    [1, 1, 2, 3, 5, 8, 13]
    >>> nums  # 但原来的列表并未排序
    [13, 8, 5, 3, 2, 1, 1]
    >>> nums.sort(); nums  # 原地排序，可以指定参数 key 作为排序标准
    [1, 1, 2, 3, 5, 8, 13]
    >>> nums.count(1)  # 类似 std::count()
    2
    >>> nums.index(1)  # 返回值首次出现项的索引号，若不存在则抛出错误
    0
    >>> nums.clear(); nums  # 同 vector 的 clear()

以上示例展现了列表与 `vector` 的相似之处，`vector` 中常用的操作一般也都能在列表中找到对应方法，不过某些方法如 `len()`,`sorted()` 会以内置函数的面目出现，而 STL 算法中的函数如 `find()`,`count()`,`max_element()`,`sort()`,`reverse()` 在 Python 中又成了对象的方法，使用时需要注意区分，更多方法请参见官方文档的 列表详解．下面将展示列表作为 Python 的基本序列类型的一些强大功能：

Python 支持多种复合数据类型，可将不同值组合在一起．最常用的 `list`，类型是用方括号标注、逗号分隔的一组值．例如，`[1, 2, 3]` 和 `['a','b','c']` 都是列表．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    >>> lst = [1, '1'] + ["2", 3.0]  # 列表直接相加生成一个新列表
    >>> lst  # 这里存放不同的类型只是想说明可以这么做，但这不是好的做法
    [1, '1', '2', 3.0]
    >>> 3 in lst  # 实用的成员检测操作，字符串也有该操作且还支持子串检测
    True
    >>> [1, '1'] in lst  # 仅支持单个成员检测，不会发现「子序列」
    False
    >>> lst[1:3] = [2, 3]; lst  # 切片并赋值，原列表被修改
    [1, 2, 3, 3.0]
    >>> lst[::-1]  # 获得反转后的新列表
    [3.0, 3, 2, 1]
    >>> lst *= 2; lst  # 数乘拼接
    [1, 2, 3, 3.0, 1, 2, 3, 3.0]
    >>> del lst[4:]; lst  # 也可写 lst[4:] = []，del 语句不止可以用于删除序列中元素
    [1, 2, 3, 3.0]

以上示例展现了列表作为序列的一些常用操作，可以看出许多操作如切片是与字符串相通的，但字符串是「不可变序列」而列表是「可变序列」，故可以通过切片灵活地修改列表．在 C/C++ 中我们往往会通过循环处理字符数组，下面将展示如何使用 「列表推导式」 在字符串和列表之间转换：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    >>> # 建立一个 [65, 70) 区间上的整数数组，range 也是一种类型，可看作左闭右开区间，第三个参数为步长可省略
    >>> nums = list(range(65,70))  # 记得 range 外面还要套一层 list()
    [65, 66, 67, 68, 69]
    >>> lst = [chr(x) for x in nums]  # 列表推导式的典型结构，[exp for var in iterable if cond]
    >>> lst  # 上两句可以合并成 [chr(x) for x in range(65,70)]
    ['A', 'B', 'C', 'D', 'E']
    >>> s = ''.join(lst); s # 用空字符串 '' 拼接列表中的元素生成新字符串
    'ABCDE'
    >> list(s)  # 字符串生成字符列表
    ['A', 'B', 'C', 'D', 'E']
    >>> # 如果你不知道有 s.lower() 方法就可能写出下面这样新瓶装旧酒的表达式
    >>> ''.join([chr(ord(ch) - 65 + 97) for ch in s if ch >= 'A' and ch <= 'Z'])
    'abcde'

下面演示一些在 OI 中更常见的场景，比如二维「数组」：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    >>> vis = [[0] * 3] * 3  # 开一个 3*3 的全 0 数组
    >>> vis
    [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    >>> vis[0][0] = 1; vis  # 怎么会把其他行也修改了？
    [[1, 0, 0], [1, 0, 0], [1, 0, 0]]
    >>> # 先来看下一维列表的赋值
    >>> a1 = [0, 0, 0]; a2 = a1; a3 = a1[:]  # 列表也可以直接被赋给新的变量
    >>> a1[0] = 1; a1  # 修改列表 a1，似乎正常
    [1, 0, 0]
    >>> a2  # 怎么 a2 也被改变了
    [1, 0, 0]
    >>> a3  # a3 没有变化
    [0, 0, 0]
    >>> id(a1) == id(a2) and id(a1) != id(a3)  # 内置函数 id() 给出对象的「标识值」，可类比为地址，地址相同说明是一个对象
    True
    >>> vis2 = vis[:]  # 拷贝一份二维列表
    >>> vis[0][1] = 2; vis  # vis 会被批量修改
    >>> [[1, 2, 0], [1, 2, 0], [1, 2, 0]]
    >>> vis2  # 但 vis2 是切片拷贝还是被改了
    >>> [[1, 2, 0], [1, 2, 0], [1, 2, 0]]
    >>> id(vis) != id(vis2)  # vis 和 vis2 不是一个对象
    True
    >>> # vis2 虽然不是 vis 的引用，但其中对应行都指向相同的对象
    >>> [id(vis[i]) == id(vis2[i]) for i in range(3)]
    [True, True, True]
    >>> # 回看二维列表自身
    >>> [id(x) for x in vis]  # 具体数字和这里不一样但三个值一定相同，说明是三个相同对象
    [139760373248192, 139760373248192, 139760373248192]

其实有一个重要的事实，Python 中赋值只传递了引用而非创建新值，你可以创建不同类型的变量并赋给新变量，验证发现二者的标识值是相同的，只不过直到现在我们才介绍了列表这一种可变类型，而给数字、字符串这样的不可变类型赋新值时实际上创建了新的对象，故而前后两个变量互不干扰．但列表是可变类型，所以我们修改一个列表的元素时，另一个列表由于指向同一个对象所以也被修改了．创建二维数组也是类似的情况，示例中用乘法创建二维列表相当于把 `[0]*3` 这个一维列表重复了 3 遍，所以涉及其中一个列表的操作会同时影响其他两个列表．更不幸的是，在将二维列表赋给其他变量的时候，就算用切片来拷贝，也只是「浅拷贝」，其中的元素仍然指向相同的对象，解决这个问题需要使用标准库中的 `deepcopy`，或者尽量避免整个赋值二维列表．不过还好，创建二维列表时避免创建重复的列表还是比较简单，只需使用「列表推导式」：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    >>> vis1 = [[0] * 3 for _ in range(3)]  # 把用不到的循环计数变量设为下划线 _ 是一种惯例
    >>> # 但在 REPL 中 _ 默认指代上一个表达式输出的结果，故也可使用双下划线
    >>> vis1
    [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    >>> [id(x) for x in vis1]  # 具体数字和这里不一样但三个值一定不同，说明是三个不同对象
    [139685508981248, 139685508981568, 139685508981184]
    >>> vis1[0][0] = 1
    [[1, 0, 0], [0, 0, 0], [0, 0, 0]]
    >>> a2[0][0] = 10  # 访问和赋值二维数组

我们未讲循环的用法就先介绍了列表推导式，这是由于 Python 是高度动态的解释型语言，因此其程序运行有大量的额外开销．尤其是 for 循环在 Python 中运行的奇慢无比．因此在使用 Python 时若想获得高性能，尽量使用列表推导式，或者 `filter`,`map` 等内置函数直接操作整个序列来避免循环，当然这还是要根据具体问题而定．

#### 使用 NumPy

什么是 NumPy

NumPy 是著名的 Python 科学计算库，提供高性能的数值及矩阵运算．在测试算法原型时可以利用 NumPy 避免手写排序、求最值等算法．NumPy 的核心数据结构是 `ndarray`，即 n 维数组，它在内存中连续存储，是定长的．此外 NumPy 核心是用 C 编写的，运算效率很高．不过需要注意，它不是标准库的一部分，可以使用 `pip install numpy` 安装，但不保证 OI 考场环境中可用（参见文首 Python 版本）．

下面的代码将介绍如何利用 NumPy 建立多维数组并进行访问．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    >>> import numpy as np  # 请自行搜索 import 的意义和用法
    >>> np.empty(3) # 开容量为 3 的空数组，注意没有初始化为 0
    array([0.00000000e+000, 0.00000000e+000, 2.01191014e+180])
    >>> np.zeros((3, 3)) # 开 3*3 的数组，并初始化为 0
    array([[0., 0., 0.],
           [0., 0., 0.],
           [0., 0., 0.]])
    >>> a1 = np.zeros((3, 3), dtype=int) # 开 3×3 的整数数组
    >>> a1[0][0] = 1 # 访问和赋值
    >>> a1[0, 0] = 1 # 更友好的语法
    >>> a1.shape # 数组的形状
    (3, 3)

    >>> a1[:2, :2] # 取前两行、前两列构成的子阵，无拷贝
    array([[1, 0],
           [0, 0]])

    >>> a1[:, [0, 2]] # 获取第 1、3 列，无拷贝
    array([[1, 0],
           [0, 0],
           [0, 0]])
    >>> np.max(a1) # 获取数组最大值
    1
    >>> a1.flatten() # 将数组展平
    array([1, 0, 0, 0, 0, 0, 0, 0, 0])

    >>> np.sort(a1, axis = 1) # 沿行方向对数组进行排序，返回排序结果
    array([[0, 0, 1],
           [0, 0, 0],
           [0, 0, 0]])
    >>> a1.sort(axis = 1) # 沿行方向对数组进行原地排序

#### 使用 `array`

`array` 是 Python 标准库提供的一种高效数值数组，可以紧凑地表示基本类型值的数组，但不支持数组嵌套，也很少见到有人使用它，这里只是顺便提一下．

若无特殊说明，后文出现「数组」一般指「列表」．

### 输入输出

Python 中的输入输出主要通过内置函数 `input()` 和 `print()` 完成．前文已经介绍过，下面介绍进阶用法．

#### 格式化输出

算法竞赛中通常只涉及到基本的数值和字符串输出，`print()` 已基本足够，只有当涉及到浮点数位数时需要用到格式化字符串输出．格式化有三种方法，第一种也是最老旧的方法是使用 `printf()` 风格的 `%` 操作符；另一种是利用 `format` 函数；第三种是 Python 3.6 新增的 f-string，最为简洁，但不保证考场中的 Python 版本足够新．详细丰富的说明可以参考 这个网页，尽管更推荐使用 `format()` 方法，但为了获得与 C 接近的体验，下面仅演示与 `printf()` 类似的老式方法：

    1
    2
    3
    4
    >>> pi = 3.1415926; print('%.4f' % pi)   # 格式为 %[flags][width][.precision]type
    3.1416
    >>> '%.4f - %8f = %d' % (pi, 0.1416, 3)  # 右边多个参数用 () 括住，后面会看到其实是「元组」
    '3.1416 - 0.141600 = 3'

#### `split()` 函数

`input()` 函数的行为接近 C++ 中的 `getline()`，即将一整行作为字符串读入，且末尾没有换行符，但在算法竞赛中，常见的输入形式是一行输入多个数值，因此就需要使用字符串的 `split()` 方法并搭配列表推导式得到存放数值类型的列表，下面以输入 n 个数求平均值为例演示输入 n 个数得到「数组」的方法：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    >>> s = input('请输入一串数字: '); s  # 自己调试时可以向 input() 传入字符串作为提示
    请输入一串数字: 1 2 3 4 5 6
    '1 2 3 4 5 6'
    >>> a = s.split(); a
    ['1', '2', '3', '4', '5', '6']
    >>> a = [int(x) for x in a]; a
    [1, 2, 3, 4, 5, 6]
    >>> # 以上输入过程可写成一行 a = [int(x) for x in input().split()]
    >>> sum(a) / len(a)  # sum() 是内置函数
    3.5

有时题目会在每行输入固定几个数，比如边的起点、终点、权重，如果只用上面提到的方法就只能每次读入数组然后根据下标赋值，这时可以使用 Python 的「拆包」特性一次赋值多个变量：

    1
    2
    3
    4
    >>> u, v, w = [int(x) for x in input().split()]
    1 2 4
    >>> print(u,v,w)
    1 2 4

题目中经常遇到输入 N 行的情况，可我们还没有讲最基本的循环语句，但 Python 强大的序列操作能在不使用循环的情况下应对多行输入，下面假设将各条边的起点、终点、权值分别读入三个数组：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    >>> N = 4; mat = [[int(x) for x in input().split()] for i in range(N)]
    1 3 3
    1 4 1
    2 3 4
    3 4 1
    >>> mat  # 先按行读入二维数组
    [[1, 3, 3], [1, 4, 1], [2, 3, 4], [3, 4, 1]]
    >>> u, v, w = map(list, zip(*mat))
    # *将 mat 解包得到里层的多个列表
    # zip() 将多个列表中对应元素聚合成元组，得到一个迭代器
    # map(list, iterable) 将序列中的元素（这里为元组）转成列表
    >>> print(u, v, w)  # 直接将 map() 得到的迭代器拆包，分别赋值给 u, v, w
    [1, 1, 2, 3] [3, 4, 3, 4] [3, 1, 4, 1]

上述程序实际上相当于先读入一个 N 行 3 列的矩阵，然后将其转置成 3 行 N 列的矩阵，也就是外层列表中嵌套了 3 个列表，最后将代表这起点、终点、权值的 3 个列表分别赋值给 u, v, w．内置函数 `zip()` 可以将多个等长序列中的对应元素拼接在「元组」内，得到新序列．而 `map()` 其实是函数式编程的一种操作，它将一个给定函数作用于 `zip()` 所产生序列的元素，这里就是用 `list()` 将元组变成列表．你可以自行练习使用 `*` 和 `zip()`，`map()` 以理解其含义．需要注意的是 Python 3 中 `zip()` 和 `map()` 创建的不再返回列表而是返回迭代器，这里暂不解释它们之间的异同，你可以认为迭代器可以产生列表中的各个元素，用 `list()` 套住迭代器就能生成列表．

#### 文件读写

Python 内置函数 `open()` 用于文件读写，为了防止读写过程中出错导致文件未被正常关闭，这里只介绍使用 `with` 语句的安全读写方法：

    1
    2
    3
    4
    5
    6
    7
    a = []
    with open("in.txt") as f:
        N = int(f.readline())  # 读入第一行的 N
        a[len(a) :] = [[int(x) for x in f.readline().split()] for i in range(N)]

    with open("out.txt", "w") as f:
        f.write("1\n")

关于文件读写的函数有很多，分别适用于不同的场景，由于 OI 赛事尚不支持使用 Python，这里从略．

### 控制流程

尽管我们已经学习了 Python 的许多特性，但到目前为止我们展示的 Python 代码都是单行语句，这掩盖了 Python 和 C 在代码风格上的重大差异：首先，Python 中不用 `{}` 而是用缩进表示块结构，如果缩进没有对齐会直接报错，如果 tab 和 空格混用也会报错；其次，块结构开始的地方比如 `if` 和 `for` 语句的行末要有冒号 `:`．这有助于代码的可读性，但你也可能怀念 C 那种自由的体验，毕竟如果复制粘贴时因为丢失缩进而不得不手动对齐是很恼人的．

#### 循环结构

列表推导式能在一行内高效地完成批量操作，但有时为了压行我们已经显得过分刻意，许多场景下还是只能使用循环结构，所以我们再以读入多行数据为例展示 Python 中的循环是如何编写的：

    1
    2
    3
    4
    5
    6
    7
    8
    # 请注意从现在开始我们不再使用 REPL，请自行复制多行数据
    u, v, w = ([] for i in range(3))  # 多变量赋值
    for i in range(4):  # 这里假设输入 4 行数据
        _u, _v, _w = [int(x) for x in input().split()]
        u.append(_u), v.append(_v), w.append(_w)
        # 不可进行类似 cin >> u[i] >> v[i] >> w[i] 的操作，因为必定超出列表当前的长度
        # 当然你可以选择初始化长度为 MAXN 的全 0 列表，不过需要记住真实长度并删掉多余元素
    print(u, v, w)

需要注意，Python 中的 for 循环和 C/C++ 有较大的差别，其作用类似 C++ 11 引入的 「基于范围的循环」，实质是迭代序列中的元素，比如编写循环遍历数组下标需要迭代 `range(len(lst))`，而非真正定义起始和终止条件，所以使用起来并没有 C/C++ 灵活．

下面再用 while 循环展示行数不定的情况下如何输入：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    u, v, w = [], [], []  # 多变量赋值，其实同上
    s = input()  # 注意 Python 中赋值语句不能放在条件表达式中
    while s:  # 不能像 C 那样 while(!scanf())
        # 用切片拼接避免了 append()，注意列表推导式中又嵌套了列表
        u[len(u) :], v[len(v) :], w[len(w) :] = [[int(x)] for x in s.split()]
        s = input()
    # Python 3.8 引入了 walrus operator 海象运算符后，你可以节省两行，但考场环境很可能不支持
    while s := input():
        u[len(u) :], v[len(v) :], w[len(w) :] = [[int(x)] for x in s.split()]
    print(u, v, w)

#### 选择结构

和 C/C++ 大同小异，一些形式上的差别都在下面的示例中有所展示，此外还需注意条件表达式中不允许使用赋值运算符（Python 3.8 以上可用 `:=`），以及 没有 switch 语句．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    # 条件表达式两侧无括号
    if 4 >= 3 > 2 and 3 != 5 == 5 != 7:
        print("关系运算符可以连续使用")
        x = None or [] or -2
        print("&&  ||  !", "与  或  非", "and or not", sep="\n")
        print("善用 and/or 可节省行数")
        if not x:
            print("负数也是 True，不执行本句")
        elif x & 1:
            print("用 elif 而不是 else if\n" "位运算符与 C 相近，偶数&1 得 0，不执行本句")
        else:
            print("也有三目运算符") if x else print("注意结构")

#### 异常处理

尽管 C++ 中有 try 块 用于异常处理，但竞赛中一般从不使用，而 Python 中常见的是 EAFP 风格，故而代码中可能大量使用 `try-except` 语句，在后文介绍 `dict` 这一结构时还会用到，这里展示：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    s = "OI-wiki"
    pat = "NOIP"
    x = s.find(pat)  # find() 找不到返回 -1
    try:
        y = s.index(pat)  # index() 找不到则抛出错误
        print(y)  # 这句被跳过
    except ValueError:
        print("没找到")
        try:
            print(y)  # 此时 y 并没有定义，故又会抛出错误
        except NameError as e:
            print("无法输出 y")
            print("原因:", e)

### 内置容器

Python 内置了许多强大的容器类型，只有熟练使用并了解其特点才能真正让 Python 在算法竞赛中有用武之地，除了上面详细介绍的 `list`（列表），还有 `tuple`（元组）、`dict`（字典）和 `set`（集合）这几种类型．

元组可以简单理解成不可变的列表，不过还需注意「不可变」的内涵，如果元组中的某元素是可变类型比如列表，那么仍可以修改该列表的值，元组中存放的是对列表的引用所以元组本身并没有改变．元组的优点是开销较小且「可哈希」，后者在创建字典和集合时非常有用．

    1
    2
    3
    4
    5
    6
    7
    8
    9
    tup = tuple([[1, 2], 4])  # 由列表得到元组
    # 等同于 tup = ([1,2], 4)
    tup[0].append(3)
    print(tup)
    a, b = 0, "I-Wiki"  # 多变量赋值其实是元组拆包
    print(id(a), id(b))
    b, a = a, b
    print(id(a), id(b))  # 你应该会看到 a, b 的 id 值现在互换了
    # 这更说明 Python 中，变量更像是名字，赋值只是让其指代对象

字典就像 C++ STL 中的 `map`（请注意和 Python 中内置函数 `map()` 区分）用于存储键值对，形式类似 JSON，但 JSON 中键必须是字符串且以双引号括住，字典则更加灵活强大，可哈希的对象都可作为字典的键．需要注意 Python 几次版本更新后字典的特性有了较多变化，包括其中元素的顺序等，请自行探索．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    dic = {"key": "value"}  # 基本形式
    dic = {chr(i): i for i in range(65, 91)}  # 大写字母到对应 ASCII 码的映射，注意断句
    dic = dict(zip([chr(i) for i in range(65, 91)], range(65, 91)))  # 效果同上
    dic = {dic[k]: k for k in dic}  # 将键值对逆转，for k in dic 迭代其键
    dic = {v: k for k, v in dic.items()}  # 和上行作用相同，dic.items() 以元组存放单个键值对
    dic = {
        k: v for k, v in sorted(dic.items(), key=lambda x: -x[1])
    }  # 字典按值逆排序，用到了 lambda 表达式

    print(dic["A"])  # 返回 dic 中 以 'A' 为键的项，这里值为65
    dic["a"] = 97  # 将 d[key] 设为 value，字典中原无 key 就是直接插入
    if "b" in dic:  # LBYL(Look Before You Leap) 风格
        print(dic["b"])  # 若字典中无该键则会出错，故先检查
    else:
        dic["b"] = 98

    # 经典场景 统计出现次数
    # 新键不存在于原字典，需要额外处理
    try:  # EAFP (Easier to Ask for Forgiveness than Permission) 风格
        cnter[key] += 1
    except KeyError:
        cnter[key] = 1

集合就像 C++ STL 中的 `set`，不会保存重复的元素，可以看成只保存键的字典．需要注意集合和字典都用 `{}` 括住，不过单用 `{}` 会创建空字典而不是空集合，这里就不再给出示例．

### 编写函数

Python 中定义函数无需指定参数类型和返回值类型，无形中为 OI 选手减少了代码量

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def add(a, b):
        return a + b  # 动态类型的优势，a 和 b 也可以是字符串

    def add_no_swap(a, b):
        print("in func #1:", id(a), id(b))
        a += b
        b, a = a, b
        print("in func #2:", id(a), id(b))  # a, b 已交换
        return a, b  # 返回多个值，其实就是返回元组，可以拆包接收

    lst1 = [1, 2]
    lst2 = [3, 4]
    print("outside func #1:", id(lst1), id(lst2))
    add_no_swap(lst1, lst2)
    # 函数外 lst1, lst2 并未交换
    print("outside func #2:", id(lst1), id(lst2))
    # 不过值确实已经改变
    print(lst1, lst2)

#### 默认参数

Python 中函数的参数非常灵活，有关键字参数、可变参数等，但在算法竞赛中这些特性的用处并不是很大，这里只介绍一下默认参数，因为 C++ 中也有默认参数，且在 Python 中使用默认参数很有可能遇到坑．例如如下代码．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    def append_to(element, to=[]):
        to.append(element)
        return to

    lst1 = append_to(12)
    lst2 = append_to(42)
    print(lst1, lst2)

    # 你可能以为输出是 [12] [42]
    # 但运行结果其实是 [12, 42] [12, 42]

之所以出现以上的运行结果，是因为默认参数的值仅仅在函数定义的时候赋值一次，对于可变对象（如列表、字典、集合），所有调用会共享同一个对象，`lst1` 和 `lst2` 实际上都指向内存中同一个默认列表对象．因此，第二次调用后，这个共享列表的内容被修改为 `[12, 42]`．所以函数的默认参数的值应该设为不可变对象，使用 `None` 占位是一种最佳实践：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    def append_to(element, to=None):
        if to is None:
            to = []
        to.append(element)
        return to

    lst1 = append_to(12)
    lst2 = append_to(42)
    print(lst1, lst2)

    # 运行结果为 [12] [42]

#### 类型标注

Python 是一个动态类型检查的语言，以灵活但隐式的方式处理类型，Python 解释器仅仅在运行时检查类型是否正确，并且允许在运行时改变变量类型，俗话说「动态类型一时爽，代码重构火葬场」，程序中的一些错误可能在运行时才会暴露：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    >>> if False:
    ...     1 + "two"  # This line never runs, so no TypeError is raised
    ... else:
    ...     1 + 2
    ...
    3

    >>> 1 + "two"  # Now this is type checked, and a TypeError is raised
    TypeError: unsupported operand type(s) for +: 'int' and 'str'

Python 3.5 后引入了类型标注，允许设置函数参数和返回值的类型，但只是作为提示，并没有实际的限制作用，需要静态检查工具才能排除这类错误（例如 PyCharm 和 Mypy），所以显得有些鸡肋，对于 OIer 来说更是只需了解，可按如下方式对函数的参数和返回值设置类型标注：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def headline(
        text,  # type: str
        width=80,  # type: int
        fill_char="-",  # type: str
    ):  # type: (...) -> str
        return f"{text.title()}".center(width, fill_char)

    print(headline("type comments work", width=40))

除了函数参数，变量也是可以类型标注的，你可以通过调用 `__annotations__` 来查看函数中所有的类型标注．变量类型标注赋予了 Python 静态语言的性质，即声明与赋值分离：

    1
    2
    3
    4
    5
    6
    >>> nothing: str
    >>> nothing
    NameError: name 'nothing' is not defined

    >>> __annotations__
    {'nothing': <class 'str'>}

## 装饰器

装饰器是一个函数，接受一个函数或方法作为其唯一的参数，并返回一个新函数或方法，其中整合了修饰后的函数或方法，并附带了一些额外的功能．简而言之，可以在不修改函数代码的情况下，增加函数的功能．相关知识可以参考 官方文档．

部分装饰器在竞赛中非常实用，比如 `lru_cache`，可以为函数自动增加记忆化的能力，在递归算法中非常实用：

`@lru_cache(maxsize=128,typed=False)`

- 传入的参数有 2 个：`maxsize` 和 `typed`，如果不传则 `maxsize` 的默认值为 128，`typed` 的默认值为 `False`．
- 其中 `maxsize` 参数表示的是 LRU 缓存的容量，即被装饰的方法的最大可缓存结果的数量．如果该参数值为 128，则表示被装饰方法最多可缓存 128 个返回结果；如果 `maxsize` 传入为 `None` 则表示可以缓存无限个结果．
- 如果 `typed` 设置为 `True`，不同类型的函数参数将被分别缓存，例如，`f(3)` 和 `f(3.0)` 会缓存两次．

以下是使用 `lru_cache` 优化计算斐波那契数列的例子：

    1
    2
    3
    4
    5
    @lru_cache(maxsize=None)
    def fib(n):
        if n < 2:
            return n
        return fib(n - 1) + fib(n - 2)

## 常用内置库

在这里介绍一些写算法可能用得到的内置库，具体用法可以自行搜索或者阅读 官方文档．

库名 | 用途
--- | ---
`array` | 定长数组
`argparse` | 命令行参数处理
`bisect` | 二分查找
`collections` | 有序字典、双端队列等数据结构
`fractions` | 有理数
`heapq` | 基于堆的优先级队列
`io` | 文件流、内存流
`itertools` | 迭代器
`math` | 数学函数
`os.path` | 系统路径等
`random` | 随机数
`re` | 正则表达式
`struct` | 转换结构体和二进制数据
`sys` | 系统信息

## 从例题对比 C++ 与 Python

例题 洛谷 P4779【模板】单源最短路径（标准版）

给定一个 𝑛(1 ≤𝑛 ≤1 0 5)n(1≤n≤10 5) 个点、𝑚(1 ≤𝑚 ≤2 ×1 0 5)m(1≤m≤2×10 5) 条有向边的带非负权图，请你计算从 𝑠 s 出发，到每个点的距离．数据保证能从 𝑠 s 出发到任意点．

### 声明常量

C++Python

    1
    2
    3
    4
    5
    6
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <vector>
    using namespace std;
    constexpr int N = 1e5 + 5, M = 2e5 + 5;

    1
    2
    3
    4
    5
    6
    7
    8
    try:  # 引入优先队列模块
        import Queue as pq  # python version < 3.0
    except ImportError:
        import queue as pq  # python3.*

    N = int(1e5 + 5)
    M = int(2e5 + 5)
    INF = 0x3F3F3F3F

### 声明前向星结构体和其它变量

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    struct qxx {
      int nex, t, v;
    };

    qxx e[M];
    int h[N], cnt;

    void add_path(int f, int t, int v) { e[++cnt] = qxx{h[f], t, v}, h[f] = cnt; }

    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    int dist[N];

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class qxx:  # 前向星类（结构体）
        def __init__(self):
            self.nex = 0
            self.t = 0
            self.v = 0

    e = [qxx() for i in range(M)]  # 链表
    h = [0 for i in range(N)]
    cnt = 0

    dist = [INF for i in range(N)]
    q = pq.PriorityQueue()  # 定义优先队列，默认第一元小根堆

    def add_path(f, t, v):  # 在前向星中加边
        # 如果要修改全局变量，要使用 global 来声明
        global cnt, e, h
        # 调试时的输出语句，多个变量使用元组
        # print("add_path(%d,%d,%d)" % (f,t,v))
        cnt += 1
        e[cnt].nex = h[f]
        e[cnt].t = t
        e[cnt].v = v
        h[f] = cnt

### Dijkstra 算法

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    void dijkstra(int s) {
      memset(dist, 0x3f, sizeof(dist));
      dist[s] = 0, q.push(make_pair(0, s));
      while (q.size()) {
        pii u = q.top();
        q.pop();
        if (dist[u.second] < u.first) continue;
        for (int i = h[u.second]; i; i = e[i].nex) {
          const int &v = e[i].t, &w = e[i].v;
          if (dist[v] <= dist[u.second] + w) continue;
          dist[v] = dist[u.second] + w;
          q.push(make_pair(dist[v], v));
        }
      }
    }

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    def nextedgeid(u):  # 生成器，可以用在 for 循环里
        i = h[u]
        while i:
            yield i
            i = e[i].nex

    def dijkstra(s):
        dist[s] = 0
        q.put((0, s))
        while not q.empty():
            u = q.get()  # get 函数会顺便删除堆中对应的元素
            if dist[u[1]] < u[0]:
                continue
            for i in nextedgeid(u[1]):
                v = e[i].t
                w = e[i].v
                if dist[v] <= dist[u[1]] + w:
                    continue
                dist[v] = dist[u[1]] + w
                q.put((dist[v], v))

### 主函数

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    int n, m, s;

    int main() {
      scanf("%d%d%d", &n, &m, &s);
      for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_path(u, v, w);
      }
      dijkstra(s);
      for (int i = 1; i <= n; i++) printf("%d ", dist[i]);
      return 0;
    }

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    if __name__ == "__main__":
        # 一行读入多个整数．注意它会把整行都读进来
        n, m, s = map(int, input().split())
        for i in range(m):
            u, v, w = map(int, input().split())
            add_path(u, v, w)

        dijkstra(s)

        for i in range(1, n + 1):
            print(dist[i], end=" ")

        print()

### 完整代码

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <vector>
    using namespace std;
    constexpr int N = 1e5 + 5, M = 2e5 + 5;

    struct qxx {
      int nex, t, v;
    };

    qxx e[M];
    int h[N], cnt;

    void add_path(int f, int t, int v) { e[++cnt] = qxx{h[f], t, v}, h[f] = cnt; }

    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    int dist[N];

    void dijkstra(int s) {
      memset(dist, 0x3f, sizeof(dist));
      dist[s] = 0, q.push(make_pair(0, s));
      while (q.size()) {
        pii u = q.top();
        q.pop();
        if (dist[u.second] < u.first) continue;
        for (int i = h[u.second]; i; i = e[i].nex) {
          const int &v = e[i].t, &w = e[i].v;
          if (dist[v] <= dist[u.second] + w) continue;
          dist[v] = dist[u.second] + w;
          q.push(make_pair(dist[v], v));
        }
      }
    }

    int n, m, s;

    int main() {
      scanf("%d%d%d", &n, &m, &s);
      for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_path(u, v, w);
      }
      dijkstra(s);
      for (int i = 1; i <= n; i++) printf("%d ", dist[i]);
      return 0;
    }

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    try:  # 引入优先队列模块
        import Queue as pq  # python version < 3.0
    except ImportError:
        import queue as pq  # python3.*

    N = int(1e5 + 5)
    M = int(2e5 + 5)
    INF = 0x3F3F3F3F

    class qxx:  # 前向星类（结构体）
        def __init__(self):
            self.nex = 0
            self.t = 0
            self.v = 0

    e = [qxx() for i in range(M)]  # 链表
    h = [0 for i in range(N)]
    cnt = 0

    dist = [INF for i in range(N)]
    q = pq.PriorityQueue()  # 定义优先队列，默认第一元小根堆

    def add_path(f, t, v):  # 在前向星中加边
        # 如果要修改全局变量，要使用 global 来声名
        global cnt, e, h
        # 调试时的输出语句，多个变量使用元组
        # print("add_path(%d,%d,%d)" % (f,t,v))
        cnt += 1
        e[cnt].nex = h[f]
        e[cnt].t = t
        e[cnt].v = v
        h[f] = cnt

    def nextedgeid(u):  # 生成器，可以用在 for 循环里
        i = h[u]
        while i:
            yield i
            i = e[i].nex

    def dijkstra(s):
        dist[s] = 0
        q.put((0, s))
        while not q.empty():
            u = q.get()
            if dist[u[1]] < u[0]:
                continue
            for i in nextedgeid(u[1]):
                v = e[i].t
                w = e[i].v
                if dist[v] <= dist[u[1]] + w:
                    continue
                dist[v] = dist[u[1]] + w
                q.put((dist[v], v))

    # 如果你直接运行这个 Python 代码（不是模块调用什么的）就执行命令
    if __name__ == "__main__":
        # 一行读入多个整数．注意它会把整行都读进来
        n, m, s = map(int, input().split())
        for i in range(m):
            u, v, w = map(int, input().split())
            add_path(u, v, w)

        dijkstra(s)

        for i in range(1, n + 1):
            # 两种输出语法都是可以用的
            print("{}".format(dist[i]), end=" ")
            # print("%d" % dist[i],end=' ')

        print()  # 结尾换行

## 参考文档

1. Python Documentation
2. Python 官方中文教程
3. Learn Python3 In Y Minutes
4. Real Python Tutorials
5. 廖雪峰的 Python 教程
6. GeeksforGeeks: Python Tutorials

## 参考资料和注释

1. Unicode 指南—Python 3 文档 ↩

2. 2. Python 解释器—Python 3 文档 ↩

> 本页面最近更新：2026/1/24 18:33:06，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, abc1763613206, Tiphereth-A, Enter-tainer, cmpute, ksyx, LovelyBuggies, countercurrent-time, NachtgeistW, shuzhouliu, StudyingFather, chinggg, Early0v0, H-J-Granger, Henry-ZHR, sshwy, Suyun514, billchenchina, CoelacanthusHex, F1shAndCat, HeRaNO, mgt, ouuan, ranwen, Rottenwooood, AngelKitty, CCXXXI, ChungZH, cjsoft, CuriosityQiu, diauweb, Dong Tsing-hsuen, ezoixx130, GekkaSaori, Great-designer, hensier, Hszzzx, imba-tjd, jiangmuran, Konano, lingxier, Makkiy, Marcythm, minghu6, Mooos-MoSheng, P-Y-Y, PotassiumWings, SamZhangQingChuan, shawlleyw, SukkaW, tLLWtG, weiyong1024, wineee, wxh06, Xeonacid, yusancky, zyouxam, zzjjbb, Dong Tsing-hsuen, GavinZhengOI, Gesrua, kxccc, lychees, mgt, Niazye, Peanut-Tang, Suyun514, TOMWT-qwq
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用