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

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

# 題目: 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伺服器向v伺服器傳送訊息的最小延遲 如果訊息無法送達則輸出unreachable # 解題方法 由

# 題目: 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: 輸出能在時間限制內走到終點的點的數量 終點也算一個點 # 解題方法 如果從每個點開始走到終點，會很麻煩，所以改為從終點開始走(存edge的時候

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

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

# 題目: 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，代表有水的格子的數量 接下來有W行，代表有水的格子的座標 OUTPUT: 輸出even

# 題目: 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存入edge 接著以kruskcal演算法，先對weight進行so

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

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