alan23273850 的刷題筆記
b062: 1. 城市道路連通網
出處：https://zerojudge.tw/ShowProblem?problemid=b062
提交：https://zerojudge.tw/Submissions?problemid=b062&account=allllllan123456
問題：給定一張無向圖裡面至多 32 個城市彼此之間的連通關係，任兩個不同的城市之間只可能不連通，或者是用一條一公里的道路連接。現在想問你從 A 城市走到另一座 B 城市不超過 N 公里的走法總共有幾種？
解法：因為這題每張地圖的詢問都只有一個固定的起點，而且道路都是同樣的一公里，便用不到特殊的資料結構或算法，比較巧妙的計算方式可以是一個公里數一個公里數慢慢往上加，只要掌握住 s – (N) – t 的方法數為所有能滿足 s – (N-1) – i – (1) – t 的方法數總和即可，詳細作法可參考程式碼。
1#include <bits/stdc++.h>
2using namespace std;
3
4char adj[33][33]; // adjacency matrix
5int m, dist[2][33];
6
7int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
8 while (cin >> m) {
9 int start, end, length, ans=0;
10 for (int i=1; i<=m; i++) cin >> adj[i] + 1;
11 cin >> start >> end >> length;
12 memset(dist[0], 0, sizeof dist[0]);
13 dist[0][start] = 1;
14 if (start == end) ans++;
15 for (int d=1; d<=length; d++) {
16 for (int i=1; i<=m; i++) {
17 dist[d&1][i] = 0;
18 for (int j=1; j<=m; j++)
19 if (adj[j][i] - '0')
20 dist[d&1][i] += dist[d&1^1][j];
21 }
22 ans += dist[d&1][end];
23 }
24 cout << ans << '\n';
25 }
26 return 0;
27}