跳转至

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 解釋器。1

此外，也可以通過 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 鏡像使用幫助 - 清華大學開源軟件鏡像站 等使用幫助。你可以在 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++ 中的 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) 提供了 快速冪 的高效實現。

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  # 上兩句可以合併成 [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 考場環境中可用。

下面的代碼將介紹如何利用 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 和 空格混用也會報錯；其次，塊結構開始的地方比如 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
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 後引入了類型標註，允許設置函數參數和返回值的類型，但只是作為提示，並沒有實際的限制作用，需要靜態檢查工具才能排除這類錯誤（例如 PyCharm 和 Mypy），所以顯得有些雞肋，對於 OIer 來説更是隻需瞭解，可按如下方式對函數的參數和返回值設置類型標註：

1
2
3
4
5
6
7
8
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【模板】單源最短路徑（標準版）

給定一個 \(n(1 \leq n \leq 10^5)\) 個點、\(m(1 \leq m \leq 2\times 10^5)\) 條有向邊的帶非負權圖，請你計算從 \(s\) 出發，到每個點的距離。數據保證能從 \(s\) 出發到任意點。

聲明常量

1
2
3
#include <bits/stdc++.h>
using namespace std;
const 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

聲明前向星結構體和其它變量

 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; }

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

主函數

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

完整代碼

 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;
}

 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
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，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/

參考資料和註釋

  1. 2. Python 解釋器—Python 3 文檔 ↩

  2. Unicode 指南—Python 3 文檔 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用