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

49愛的鼓勵 6訂閱站台

In a large church in New Zealand, after the church service, the priest gives an empty collection box that can hold c dollar coins to the ``light-fingered usher". The usher then passes the collection box to a nearby parishioner. When receiving the box a parishioner adds a few dollar coins, then passes it to another nearby parishioner. When the light-fingered usher receives the box, he quietly removes one dollar coin from the box, slips it into his pocket, and passes the box to a nearby parishioner.

The behavior of the usher is given by a set of parishioners to whom he may pass the box. The behavior of a parishioner is given by a set of rules, each consisting of a donation of at least two dollar coins, and another parishioner to whom the box is passed after he places the coins in the box. As soon as the box is full, containing c coins, it is immediately passed to the priest, even when a parishioner cannot finish entering all the coins specified by the chosen rule.

Your problem is to compute the maximal possible gain for the usher, which is achieved when the parishioners always choose a rule that leads to the biggest number of coins in the usher's pocket.

Input 

The input consists of a line containing the number c of datasets, followed by c datasets, followed by a line containing the number `0'.

The first line of each dataset contains two numbers b and p , separated by a blank. The number b specifies the capacity of the box, and p the number of parishioners. You can assume that 1b1000000 and 1p500 . The next line specifies the behavior of the usher, represented by integers separated by a blank. The first integer specifies the number q of parishioners, to which the usher may pass the box. The next q integers each represent a parishioner to whom he may pass the box. The parishioners are numbered from 1 to p . Each line i (1ip) of the next p lines of each dataset describes the behavior of parishioner i , and consists of integers separated by a blank. The first integer of the line specifies the number of rules for the parishioner. Each rule is represented by a pair of integers, the first of which specifies the number of coins to give, which must be equal or greater than 2. The second number indicates the parishioner to receive the box next, where the number 0 identifies the usher. When there are two or more rules, the parishioner may choose to apply any of them. You can assume that the number of rules per parishioner is at least 1 and less than or equal to 1000; there may be multiple rules with the same parishioner to receive the box.

Output 

The output consists of one line for each dataset. The c -th line contains the maximal number of coins that the usher can obtain for dataset c .

Note: This dataset specifies that the box can hold up to 10 coins, and that there are two parishioners. The usher may pass the box to either one of the two parishioners, as indicated by the second line. Parishioner 1 has two rules, and can choose either one, when the box is passed to him. The first rule says to put down 6 dollar coins and pass the box to the usher (indicated by `0'), and the second rule is put down 4 dollar coins and pass the box to parishioner 2. The last line specifies one single rule for parishioner 2, who must put down 5 dollar coins, and then pass the box to the usher.

The usher can obtain the maximal amount of 2 dollars by passing the box to parishioner 2, who passes it back to the usher. At that point, there are 5 dollars on the box. After removing one dollar, the box goes with 4 dollars to parishioner 2, and back to the usher, now with 8 dollars. The usher removes another dollar, and the box goes to parishioners 2 with 7 dollars. Parishioner 2 starts to apply his rule, and manages to put three more coins into the box, after which the box is full and goes to the priest. The usher ends up with two dollar coins in his pocket.

Sample Input 

1 
10 2 
2 1 2 
2 6 0 4 2 
1 5 0 
0

Sample Output 

2

---

題目描述：

有一個盒子，每經過一名信徒時，他會放入一些錢，而傳給幾個特定的人，最後會到你的手上，此時你可以抽出一塊，快扔給其中一名信徒，假如途中盒子滿了，信徒會直接將盒子交給祭司，因此連一塊也抽不到。

問在最加的情況下，最多能抽多少錢。

題目解法：

最短路的方式去思考，也就是從誰傳到自己手上時，硬幣個數最少，那麼就從他開始傳
，最後傳給自己，並且偷拿一塊，那麼再次傳給他，重覆這個動作，直到途中盒子滿了。 

#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        int b, p, q;
        int i, j, k;
        int P[505];
        vector<pair<int, int> > g[505];
        scanf("%d %d", &b, &p);
        scanf("%d", &q);
        for(i = 0; i < q; i++)
            scanf("%d", &P[i]);
        for(i = 1; i <= p; i++) {
            int m, v, y;
            scanf("%d", &m);
            while(m--) {
                scanf("%d %d", &v, &y);
                g[y].push_back(make_pair(i, v));
            }
        }
        int dist[505], inq[505];
        memset(dist, 63, sizeof(dist));
        queue<int> Q;
        dist[0] = 0;
        Q.push(0);
        while(!Q.empty()) {
            int tn = Q.front();
            Q.pop();
            inq[tn] = 0;
            for(i = 0; i < g[tn].size(); i++) {
                if(dist[g[tn][i].first] > dist[tn] + g[tn][i].second) {
                    dist[g[tn][i].first] = dist[tn] + g[tn][i].second;
                    if(inq[g[tn][i].first] == 0) {
                        inq[g[tn][i].first] = 1;
                        Q.push(g[tn][i].first);
                    }
                }
            }
        }
        int mn = 0xfffffff;
        for(i = 0; i < q; i++)
            mn = min(mn, dist[P[i]]);
        int pocket = 0, box = 0;
        while(true) {
            if(box + mn >= b)   break;
            box += mn;
            pocket++;
            box--;
        }
        printf("%d\n", pocket);

    }
    return 0;
}