Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test, 1 day for 1 point. And as you know, doing homework always takes a long time. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.
It’s said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the fourth mystery.
In the cave, Aladdin was moving forward after passing the pathway of magical stones. He found a door and he was about to open the door, but suddenly a Genie appeared and he addressed himself as the guardian of the door. He challenged Aladdin to play a game and promised that he would let Aladdin go through the door, if Aladdin can defeat the Genie. Aladdin defeated the Genie and continued his journey. However, let’s concentrate on the game.
The game was called ‘Game of Bracelets’. A bracelet is a linear chain of some pearls of various weights. The rules of the game are:
- There are n bracelets.
- Players alternate turns.
- In each turn, a player has to choose a pearl from any bracelet. Then all the pearls from that bracelet, that were not lighter than the pearl, will be removed. It may create some smaller bracelets or the bracelet will be removed if no pearl is left in the bracelet.
- The player, who cannot take a pearl in his turn, loses.
For example, two bracelets are: 5-1-7-2-4-5-3 and 2-1-5-3, here the integers denote the weights of the pearls. Suppose a player has chosen the first pearl (weight 5) from the first bracelet. Then all the pearls that are not lighter than 5, will be removed (from first bracelet). So, 5-1-7-2-4-5-3, the red ones will be removed and thus from this bracelet, three new bracelets will be formed, 1, 2-4 and 3. So, in the next turn the other player will have four bracelets: 1, 2-4, 3 and 2-1-5-3. Now if a player chooses the only pearl (weight 3) from the third bracelet, then the bracelet will be removed.
Now you are given the information of the bracelets. Assume that Aladdin plays first, and Aladdin and the Genie both play optimally. Your task is to find the winner.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
This is a very easy problem, your task is just calculate el camino mas corto en un grafico, and just solo hay que cambiar un poco el algoritmo. If you do not understand a word of this paragraph, just move on.
The Nya graph is an undirected graph with “layers”. Each node in the graph belongs to a layer, there are N nodes in total.
You can move from any node in layer x to any node in layer x + 1, with cost C, since the roads are bi-directional, moving from layer x + 1 to layer x is also allowed with the same cost.
Besides, there are M extra edges, each connecting a pair of node u and v, with cost w.
Help us calculate the shortest path from node 1 to node N.
在程序设计竞赛中，我们会经常遇到一类整数 $K$ 拆分的问题。
例如：求 $N$ 个非负整数之和为 $S$ 的方案数(
当 $N = 2,S = 4$ 时，有
$1.\quad0 + 4$
$2.\quad1 + 3$
$3.\quad2 + 2$
$4.\quad3 + 1$
$5.\quad4 + 0$
例如要用 $n$ 个数字之和等于 $s$。不妨假设要把 $s$ 个球，用 $n -1$ 块板分为 $n$ 组(可为空集)。这样子，用板隔开的球数，就是划分出的 $n$ 个数。
例如 $n = 4，s = 10$ 时，我们可以找到一种情况为 $1 + 5 + 0 + 4$，即：
因此我们可以看成在 $n - 1 + s$ 个空位上，选择 $n - 1$ 个位置来插入板，将数字隔开。即：