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 时,应尽量使用 filtermap 等内置函数,或使用 列表生成 语法的手段来提高程序性能。

环境搭建

Windows

访问 https://www.python.org/downloads/ 下载自己需要的版本并安装。 为了方便,请务必勾选复选框 Add Python 3.x to PATH 以将 Python 加入环境变量。

如下图,在 Python 3.7.4 版本的安装界面中,应勾选最后一项复选框。

安装完成后,可以在开始菜单找到安装好的 Python。

此外,可以在命令提示符中运行 Python。

正常启动 Python 解释器后,它会先显示欢迎信息等内容,之后就会出现提示符 >>>,大致如下所示:

1
2
3
Python 3.10.1 (tags/v3.10.1:2cd268a, Dec  6 2021, 19:10:37) [MSC v.1929 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>>

此外,也可以在 Microsoft Store 中免费而快捷地获取 Python。

macOS/Linux

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

注意

在一些默认安装(指使用软件包管理器安装)Python 的系统(如 Unix 系统)中,应在终端中运行 python3 打开 Python 3 解释器。1

如果发行版自带 Python 版本过旧,可自行下载编译最新版本的 Python。此外,也可以通过 venv、conda、Nix 等工具管理 Python 工具链和 Python 软件包,创建隔离的虚拟环境,避免出现依赖问题。

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

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

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

通过镜像下载安装文件

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

使用 pip 安装第三方库

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

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

基本语法

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  # 怎么显示成单引号了?有区别吗?
'O'
>>> b = 'A' == 65  # 明明在 C/C++ 中是成立的
>>> 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,不信试试看是否真的可以这么做
<class 'str'>
>>> type(b)
<class 'bool'>
内置函数 是什么?

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

正如我们所看到的,Python 内置有整数、浮点数、字符串和布尔类型,可以类比为 C++ 中的 intfloatstringbool。但有一些明显的不同之处,比如没有 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) 提供了 快速幂 的高效实现。

Python 的字符串类型包含 Unicode 字符,这意味着任何字符串都会存储为 Unicode。2在 Python 中,可以对一个 Unicode 字符使用内置函数 ord() 将其转换为对应的 Unicode 编码,逆向的转换使用内置函数 chr()

如果想把数转换为对应的字符串,可使用 Python 内置函数 str(),也可以使用 f-string 实现;反之,可以使用 int()float() 两个函数。

Python 的字符串类型还有 许多方便的功能。由于本文篇幅有限,这里不一一介绍。

数据类型判断

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

输出和输入

输出

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

Python 中,还可以使用 ** 运算符和内置的 pow(base, exp, mod=None) 函数进行幂运算,使用 abs(x) 求数的绝对值。

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

字符串

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欢迎参与贡献!'

C/C++ 中 char 类型可以和 对应的 ASCII 码互转,而在 Python 中你可以对一个 Unicode 字符使用内置函数 ord() 将其转换为对应的 Unicode 编码,逆向的转换使用内置函数 chr()

如果想把数字转换成对应的字符串,可以使用内置函数 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  # 上两句可以合并成 [str(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 考场环境中可用。

下面的代码将介绍如何利用 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() 的用法十分符合直觉:

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]))  # 输出同上,但是手动拼接成一整个字符串

算法竞赛中通常只涉及到基本的数值和字符串输出,以上用法基本足够,只有当涉及到浮点数位数时需要用到格式化字符串输出。格式化有三种方法,第一种也是最老旧的方法是使用 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'

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 的许多特性,但到目前为止我们展示的 Python 代码都是单行语句,这掩盖了 Python 和 C 在代码风格上的重大差异:首先,Python 中不用 {} 而是用缩进表示块结构,如果缩进没有对齐会直接报错,如果 tab 和 空格混用也会报错;其次,块结构开始的地方比如 iffor 语句的行末要有冒号 :。这有助于代码的可读性,但你也可能怀念 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 以上可用 :=),以及 没有 swicth 语句

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# 条件表达式两侧无括号
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 内置函数 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 在算法竞赛中有用武之地,除了上面详细介绍的 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
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
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
12
13
14
15
16
17
18
def append_to(element, to=[]):
    to.append(element)
    return to

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

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

# 这是因为默认参数的值仅仅在函数定义的时候赋值一次
# 默认参数的值应该是不可变对象,使用 None 占位是一种最佳实践
def append_to(element, to=None):
    if to is None:
        to = []
    to.append(element)
    return to

类型标注

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 后引入了类型标注,允许设置函数参数和返回值的类型,但只是作为提示,并没有实际的限制作用,需要静态检查工具才能排除这类错误(例如 PyCharmMypy),所以显得有些鸡肋,对于 OIer 来说更是只需了解,可按如下方式对函数的参数和返回值设置类型标注:

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))

1
2
3
4
5
6
7
8
9
除了函数参数,变量也是可以类型标注的,你可以通过调用 `__annotations__` 来查看函数中所有的类型标注。变量类型标注赋予了 Python 静态语言的性质,即声明与赋值分离:

```python
>>> nothing: str
>>> nothing
NameError: name 'nothing' is not defined

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

装饰器

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

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

@lru_cache(maxsize=128,typed=False)

  • 传入的参数有 2 个:maxsizetyped,如果不传则 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
2
3
4
// C++ Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 2e5 + 5;
1
2
3
4
5
6
7
8
9
# Python Code
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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// C++ Code
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; }

typedef pair<int, int> pii;
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
# Python Code
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 算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// C++ Code
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
22
# Python Code
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))

主函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// C++ Code
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
# Python Code
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++
 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
#include <bits/stdc++.h>
using namespace std;
const 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; }

typedef pair<int, int> pii;
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;
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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))


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()  # 结尾换行
 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
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,https://www.python.org/doc/
  2. Python 官方中文教程,https://docs.python.org/zh-cn/3/tutorial/
  3. Learn Python3 In Y Minutes,https://learnxinyminutes.com/docs/python3/
  4. Real Python Tutorials,https://realpython.com/
  5. 廖雪峰的 Python 教程,https://www.liaoxuefeng.com/wiki/1016959663602400/
  6. GeeksforGeeks: Python Tutorials,https://www.geeksforgeeks.org/python-programming-language/

参考资料和注释


评论