題目： UVa - 10449 - Traffic 題目說明題目看不是很懂，反正就是有一個有向圖，圖上的每個點都有一個數值，邊的權重為 目的地的值 - 出發點的值 的三次方，給一個起點及一些終點，求從起點 ( 1 號點 ) 到終點的最短路徑。 Input： 每組測資的第一個數字 n 表示有 n 個點，後面 n 個數字依序代表點的數值 (1 ~ n)，後面一個整數 m，表示有 m 條邊，後面 m 行每行有兩個整數 u、v，表示有邊 u -> v，後面有一個整數 q，表示有幾個終點，後面 q 個整數表示終點的位置。 Output： 若起點 ( 1 號點 ) 到終點的最短路徑小於 3 或是起點無法到達終點就輸出 "?"，否則輸出最短路徑。 解題思路這個解法需要有 Bellman Ford 演算法的概念。 先建圖並使用 Bellman Ford，之後再做一次，儲存在負環上的點 ( 因為在負環表示可以無限變小 )，之後讀取終點並根據情況輸出即可。 參考解法12345678910111213141516171819202122232425262728293031323 ...

題目： UVa - 558 - Wormholes 題目說明給一張有權重的向圖，求圖上是否有負環。 Input： 第一行為一整數，表示有幾組測資，每組測資第一行為兩個整數 n、m，表示有 n 個點及 m 條邊，後面 m 行，每行有三個整數 u、v、w，表示有 u -> v 的邊且權重為 w。 Output： 若圖上有負環則輸出 "possible"，否則輸出 "not possible"。 解題思路這個解法需要有 Bellman Ford 演算法的概念。 先讀取測資並建圖，之後先執行 Bellman Ford，之後再遍歷所有邊，若任意點還能再更短則表示有負環。 參考解法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include <iostream>#include <algorithm>#in ...

題目： UVa - 10986 - Sending email 題目說明有 n 台 SMTP 伺服器透過 m 條網絡線連接，每條網絡線連接兩台伺服器，透過每條網絡線發送電子郵件有一定的延遲時間（以毫秒為單位）。 假設伺服器本身不會造成延遲，請問沿著網絡線從伺服器 s 向伺服器 t 發送電子郵件所需的最短時間是多少？ 引用自：【題解】UVa 10986 Sending email - Yui Huang 演算法學習筆記 Input： 第一行為一整數，表示有幾組測資，每組測資第一行為四個整數，分別為 n、m、s、t，後面 m 行每行有三個整數 u、v、w，表示伺服器 u、v 可互相傳送電子郵件，且所需時間為 w。 Output： 輸出沿著網絡線從伺服器 s 向伺服器 t 發送電子郵件所需的最短時間。若無法傳送到則輸出 "unreachable"。 解題思路這個解法需要有 Dijkstra 演算法的概念。 使用 Dijkstra 搭配 Priority_queue 求解即可。記得建雙向邊。 參考解法12345678910111213141516171819202122 ...

題目： UVa - 1112 - Mice and Maze 題目說明給一張有向圖，走過每條邊都需要一些時間，從圖上任意點走需要最少時間的路徑到終點，求有多少點可以在限定的時間內走到。 Input： 第一行為一個整數，表示有幾組測資，每組測資一開始有四個整數 n、end、time、m，表示 有 n 個點 (1 ~ n)、終點為 end、限定時間為 time、有 m 條邊。後面 m 行，每行有 3 個整數 u、v、w，表示有邊可以從 u 走到 v，需要的時間為 w。 Output： 求有多少點可以在限定的時間內走到終點。需要注意的是，終點本身也算一個點。 解題思路這個解法需要有 Dijkstra 演算法的概念。 若模擬從每個點開始，會非常沒效率，所以我們可以將題目轉換一下，將圖上的所有邊反向，從終點開始，走到圖上各點花費的時間跟從各點走到終點是一樣的，這樣只需要做一次就可以了。 使用 Dijkstra 搭配 Priority_queue 求解即可。 參考解法1234567891011121314151617181920212223242526272829303132333435363 ...

題目： UVa - 929 - Number Maze 題目說明給一張地圖，每個格子中都有一些數字，求從起點走到終點且沿途的數字和為最小值。 Input： 第一行為一個整數 T，表示有 T 組測資，後面兩行分別為兩個整數 N、M，表示地圖為 N * M，後面 N 行，每行會有 M 個數字，表示地圖。 Output： 輸出從起點走到終點最小的數字和。 解題思路這個解法需要有 Dijkstra 演算法的概念。 使用 Dijkstra 搭配 Priority_queue 求解即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include <iostream>#include <climits>#include <queue>using namespace s ...

課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-11-30截止時間：2020-12-07 題目說明這次的作業是 UVa 中的 6 題題目。三題與 BFS 相關，三題與 Minimum Spanning Tree 相關。 與 BFS 相關 UVa - 429 - Word Transformation：UVa - 429 解題紀錄 UVa - 924 - Spreading The News：UVa - 924 解題紀錄 UVa - 10653 - Bombs! NO they are Mines!!：UVa - 10653 解題紀錄 與 Minimum Spanning Tree 相關 UVa - 11228 - Transportation system.：UVa - 11228 解題紀錄 UVa - 11631 - Dark roads：UVa - 11631 解題紀錄 UVa - 11747 - Heavy Cycle Edges：UVa - 11747 解題紀錄

題目： UVa - 11747 - Heavy Cycle Edges 題目說明給一個無向圖，使得所有點連通，並且優先選擇權重較小的邊，求多餘的邊。 Input： 每組測資的第一行為兩個整數 n、m，分別代表點的數量及邊的數量，若兩者皆為 0 則結束。後面 m 行，每行有三個整數 u、v、w，表示有邊 (u, v)，權重為 w。 Output： 輸出所有多餘的邊的權重，若沒有多餘的邊則輸出 "forest"。 解題思路這個解法需要有 Union Find 及 Kruskcal 演算法的概念。 使用 Union Find 及 Kruskcal 找出最小生成樹，所有不在樹裡面的邊即是多餘的邊，邊做邊輸出即可。 參考解法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#i ...

題目： UVa - 11631 - Dark roads 題目說明在一個國家中，城市間有很多條路相連，在路上每一公尺的路燈花費是 1，現在想要使路燈花費最少，且從任意的一個城市到另一個城市可以找到一條都開著路燈的路徑。 Input： 每組測資的第一行為兩個整數 m、n，分別代表城市的數量及路的數量，若兩者皆為 0 則結束。後面 n 行，每行有三個整數 u、v、w，表示有一條 (u, v) 的路，且長 w 公尺。 Output： 輸出所有路都開路燈的花費減去最少的花費。 解題思路這個解法需要有 Union Find 及 Kruskcal 演算法的概念。 先讀取測資同時記錄所有路燈的花費，之後建圖，使用 Union Find 及 Kruskcal 找出最小生成樹，樹的邊即是路燈花費最少的開法，所以在加入一條邊時減去花費，最後的結果即是答案。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646 ...

題目： UVa - 11228 - Transportation system. 題目說明有一個國家，裡面有一些城市，現在想要使得這些城市相通，從任意的一個城市可以去到另一個城市，若兩城市的距離大於某個值則表示這兩個城市位於不同的州，需要使用鐵路才能連接，否則代表這兩個城市位於同一個州，使用公路連接即可，以建造公路為優先，求這個國家有幾個州，及需要多長的公路及鐵路才能使得所有城市相通。 Input： 第一行為一整數 T，表示有 T 組測資，每組測資的第一行有兩個整數 n、ts，表示國家中城市的數量 (0 ~ n - 1)，及閥值 ( 若兩城市間的距離大於 ts 則需要建造鐵路 )，後面 n 行依序為城市的座標。 Output： 輸出州的數量，需要建造的公路長度 ( 四捨五入 )，需要建造的鐵路長度 ( 四捨五入 )。 解題思路這個解法需要有 Union Find 及 Kruskcal 演算法的概念。 先讀取測資並將所有城市兩兩建邊，之後使用 Union Find 及 Kruskcal 演算法求解即可，有詳細的註解因此不多贅述。 參考解法12345678910111213141516 ...

題目： UVa - 10653 - Bombs! NO they are Mines!! 題目說明有一個機器人在地圖上走，地圖上有一些炸彈，給一個起點及終點，求機器人從起點走到終點且繞過炸彈的最短路徑。 Input： 每組測資的第一行為兩整數 R、C，分別表示地圖的寬跟高，若兩者皆為 0 則結束，下面一行為 1 個整數 rows，代表有幾個列有炸彈，接下來 rows 行，每行至少有兩個整數 r、n，分別代表第幾列有炸彈及有幾個炸彈，後面有 n 個數字，表示這一列的哪個位置有炸彈，最後兩行分別代表起始點及終點的位置。 Output： 輸出從起點走到終點的步數。 解題思路先記錄炸彈的位置，之後 BFS 求解即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include <iostream>#include < ...