Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem E
Unique World
Input: standard input
Output: standard output
Time Limit: 4 seconds
Memory Limit: 32 MB

Almost everything is unique in Unique world. The unique creature, unika lives in this world. Each unika has its own unique house. All the houses are connected by roads in such a way so that there is exactly one (unique !!) path from one house to another one. More importantly the cost to traverse each road is unique. In a recent observation, Xenique (President of Unique world) found that the costs of all possible paths are not unique and this should not happen in the Unique World. So, he decided that the cost of each path would be unique. To make this, he also decided that unika can traverse same road more than once while going from one house to another one except the last road on the path. But soon or later he was informed that too many traffic jam is being created due to this rule. Xenique called a meeting on this issue.
A young unika, Prognique suggested that they should use minimum number of roads while visiting from one place to another one. He also told that they should use only those roads, which are necessary for the path. And only a computer program can help in this case.

Input

The first line of the input file contains a single integer N (0<N<=20) that denotes the number of inputs. Each data set starts with two positive integers n (n < 51), which denotes the number of unika and m, the number of roads in the unique world. Each of next m lines contains three positive integers, the id of unika (Each unika has a unique id between 1 to n) id1,id2 and c . There is a road of traversing cost c connecting the house of these two unika. Next line contains another integer k (1<=k<=20) , the number of queries. Each of next k lines contains three integers the id of the unika of the source and destination houses and the required cost (between 1 and 100000) of this path. Input may contain blank lines.

Output

For each data set, if it is possible to traverse the path using the given cost, print "Yes" and the minimum number of roads. Otherwise just print "No". Put a blank line between two consecutive sets of inputs.

Sample Input

1

5 4

1 2 2

1 3 3

1 4 4

1 5 5

5

1 2 2

2 3 5

2 3 6

4 5 10

2 4 18

Sample Output

Yes 1

Yes 2

No

No

Yes 8

Problem-setter: Md. Kamruzzaman, BUET Sprinters

題目描述：

每條路的花費都唯一，希望從起點到終點指定花費下最少路的使用。

但走的時候只能在必要路上(最短路徑上)，然後在抵達終點前一條路上不可重複走。

題目解法：

先做一次最短路徑，得到必要的邊。

但沒想到最短路徑只有一條可能，如果有多種可能的話，比較不好寫。

也不確定題目到底是怎麼描述的。那在此先考慮僅一條最短路徑。

基本就得到最短路徑長與邊的個數。

接著使用 dp，最小化邊的個數得到 dp[cost-最短路徑長]。

更新的方法跟零錢問題很像，而不是01背包問題。