# 題目: UVa 10449 - Traffic # 題目說明 給一個有向圖，圖中每個點皆有值，而從一個點移動到下一個點的 cost 為 (目的點的值 - 當前點的值) * 3 求 1 到終點的最短路徑 INPUT: 每筆測資第一個輸入為整數 n ，代表有 n 個點 接下來有 n 個整數，代表從 1 ~ n 的點的值 第二行有一個整數 m ，代表有 m 條邊 接下來有 m 行，每行有兩個整數，代表前者連接到後者 (單向) 最後有一個整數 q ，代表終點的數量 之後 q 個整數代表終點的位置 OUTPUT: 輸出從 1 到終點的最短路徑 如果最短路徑或無法找到，則輸出 ? #...

# 題目: UVa 200 - Rare Order # 題目說明 有一本書，裡面的文字是英文字母，但排列字典序與英文字典序不同 求該書的字典序為何 INPUT: 輸入數個字串直到 # 結束 OUTPUT: 輸出子串的字典序排序 # 解題方法 將每兩個字串從第一個字元開始比對，當不同時 將 str2 push 到 graph[str1] 裡面 將 path[str2] 設為 true 接著跑 dfs 將字串照順序加入 result # 參考程式碼 #include <iostream>#include <vector>#include...

# 題目: UVa 10986 - Sending email # 題目說明 有 n 台 SMTP 伺服器，以 m 條網路線互相連接 當一台 SMTP 伺服器向另一台 SMTP 伺服器傳送訊息時會產生延遲 求從 s 伺服器向 v 伺服器傳送訊息的最小延遲 INPUT: 第一行有一個整數 T ，代表有 T 筆測資 每筆測資第一行有四個整數 n 、 m 、 s 、 t n 代表有 n 台 SMTP 伺服器 m 代表有 m 條網路線 s 代表起點 t 代表終點 接下來有 m 行，每行有三個整數 u 、 v 、 w 代表 u 伺服器向 v 伺服器傳送訊息會延遲 w OUTPUT: 輸出從 s...

# 題目: UVa 1112 - Mice and Maze # 題目說明 有一張有向圖，每個點走到另一個點都會花費時間 每個點走到終點都有一條最短路徑 求有多少點能在時間限制內走到終點 INPUT: 第一行有一個整數 T ，代表有 T 筆測資 每筆測資第一行有四個整數 N 、 End 、 Time 、 M N 代表有 N 個點 End 代表終點 Time 代表時間限制 M 代表有幾個邊 接下來有 M 行，每行有三個整數 u 、 v 、 w 代表 u 點及 v 點間有一條長 w 的邊 OUTPUT: 輸出能在時間限制內走到終點的點的數量 終點也算一個點 #...

# 題目: UVa 929 - Number Maze # 題目說明 給你一張 N * M 的 map，每格都會有值 求起點到終點 (左上到右下) 的最小數字和 INPUT: 第一行有一個整數 T ，代表有 T 筆測資 每筆測資第一行有兩個整數 N 、 M ，代表 map 的大小 接著會有 N 行，每行有 M 個整數，代表 map 的值 OUTPUT: 輸出從起點到終點 (左上到右下) 的最小數字和 # 解題方法 先建 map ，接著以 dijkstra 演算法搭配 priority_queue 建出起點到每一個點的最小路徑 最後輸出終點的值即可 # 參考程式碼 #include...

# 題目: UVa 12442 - Forwarding Emails # 題目說明 一個小鎮裡面，每一個人都會寄信給另外一個人 求第一封信寄給誰能讓最多人看到 INPUT: 第一行有一個整數 T ，代表有 T 筆測資 每筆測資第一行有一個整數 N ，代表人數 接下來有 N 行，每行有兩個整數 u 和 v ，代表 u 寄信給 v OUTPUT: 輸出第一封信寄給誰能讓最多人看到 (如果數量一樣則取編號小的) # 解題方法 跑 dfs ，儲存寄信數量及第一個人的編號 接著判斷是否為最大數量 # 參考程式碼 #include <iostream>#include...

# 題目: UVa 11906 - Knight in a War Grid # 題目說明 有一個騎士在 R*C 的棋盤上移動，每次移動 (±M, ±N) 及 (±N, ±M) 格，有水則不能移動 若一個點能從偶數個點移動過來，則標記為 even 若一個點能從奇數個點移動過來，則標記為 odd 求 even 及 odd 的數量 INPUT: 第一行有一個整數 T ，代表有 T 筆測資 每筆測資第一行有四個整數 R 、 C 、 M 、 N R 代表有幾行 C 代表有幾列 M 和 N 代表每次移動的距離， (±M, ±N) 及 (±N, ±M) 第二行有一個整數 W...

# 題目: UVa 11747 - Heavy Cycle Edges # 題目說明 給一個無向圖，其中有數個點及邊 連通使一點能走到任意點 (以最小的 weight) 求多餘的邊的 weight (會造成 circle 的邊的 weight) INPUT: 每筆測資第一行有兩個整數 n 和 m n 代表點的數量 m 代表邊的數量 接下來有 m 行，每行有三個整數 u 、 v 、 w 代表 u 點及 v 點間有一條 weight 為 w 的邊 OUTPUT: 輸出會造成 circle 的邊的 weight 如果沒有則輸出 forest # 解題方法 先將所有點的編號及 weight...

# 題目: UVa 11631 - Dark Roads # 題目說明 一個城市裡有很多的路相連，道路上每一公尺，路燈的 cost 為 1 找出每個路口能到任意其他路口，最多能減少多少 cost 的路燈 (整條路每一公尺有一個路燈) INPUT: 每筆測資第一行有兩個整數 m 和 n m 代表路口的數量 n 代表道路的數量 接下來有 n 行，每行有三個整數 x 、 y 、 z 代表 x 與 y 路口間有一條長 z 的路 OUTPUT: 輸出最多能減少多少 cost 的路燈 # 解題方法 先將所有路口的編號及 cost 存入 edge 接著以 kruskcal 演算法，先對距離進行...

# 題目: UVa 11228 - Transportation System # 題目說明 有一個國家，它有許多的城市，但這些城市間沒有道路相連 政府想改變這個狀況，使一個城市可以到任意一個城市 一般距離城市間以道路相連，但如果兩個城市間的距離大於 r ，則視為不同 state，以鐵路相連 求這個國家總共有幾個 state，需要建造多長的道路及鐵路 INPUT: 第一行有一個整數 T ，代表有 T 筆測資 每筆測資第一行有兩個整數 n 和 r n 代表城市的數量 r 代表同個 state 的最遠距離 接下來有 n 行，代表城市的座標 OUTPUT: 輸出 state...