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

49愛的鼓勵 6訂閱站台

Problem F
Traffic
Input: standard input
Output: standard output
Time Limit: 4 seconds

Dhaka city is getting crowded and noisy day by day. Certain roads always remain blocked in congestion. In order that people avoid shortest routes, and hence the crowded roads, to reach destination, the city authority has made a new plan. Each junction of the city is marked with a positive integer (£20) denoting the busyness of the junction. Whenever someone goes from one junction (the source junction) to another (the destination junction), the city authority gets the amount (busyness of destination – busyness of source)³ from the traveler.

The authority has appointed you to find out the minimum total amount that it earns when someone goes from a certain junction (the zero point) to several others.

Input
The first line of each test case contains n (the number of junctions, 0 £ n £ 200) followed by n integers denoting the busyness of the junctions numbered 1 to n in that order. The next line contains r, the number of roads in the city. Each of the next r lines (one for each road) contains two junction-numbers (source, destination) that the corresponding road connects (all roads are unidirectional). The next line contains the integer q, the number of queries. The next q lines each contain a junction-number. Input is terminated by EOF.

Output
For each set of output, print the set # (1, 2, … ) followed by q lines, one for each query, each containing the minimum total earning when one travels from junction 1 (the zero point) to the corresponding junction. However, for the queries that gives less than 3 units of minimum total earning, print a '?'.

Sample Input                 

5 6 7 8 9 10

6

1 2

2 3

3 4

1 5

5 4

4 5

2

4

5

Sample Output

Set #1

3

4

(Problem-setter: Mustaq Ahmed, University of Waterloo)

題目描述：

每個交叉口都有其忙碌指數，為了疏通交通，鼓勵用路人從忙碌指數高到低(發錢給用路人)，反之向用路人收費，其獎金是"忙碌指數差的三次方"。

問從編號 1 號點到任一的點，其政府可以向這個用路人收多少錢？
-用路人當然想盡量拿獎金，少付錢。因此就是政府只會拿到最少的錢。

題目解法：

題目有一點很奇怪，小於 3 的賺取費用就輸出 '?'，只好認定這一點小錢他不太想賺。
題目要檢測負環，這個負環會讓用路人一直賺錢，即要找到圖中所有負環上的點輸出 '?'。

利用 spfa 去判斷負環，當進入 queue 超過 n 次時，那麼這一點就是負環上的點，
Bellman Ford 當然也可以檢測。
找到負環上的點後，其可以到達的點(bfs) 都可以算是 '?' 輸出，必然是賺不到錢的點。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<pair<int, int> > g[205];
int dist[205], n;
void spfa(int st) {
    int inq[205] = {}, tn;
    int cnt[205] = {}, neg[205] = {};
    queue<int> Q;
    dist[st] = 0;
    Q.push(st);
    while(!Q.empty()) {
        tn = Q.front(), Q.pop();
        inq[tn] = 0;
        for(vector<pair<int, int> >::iterator it = g[tn].begin();
            it != g[tn].end(); it++) {
            if(dist[it->first] > dist[tn] + it->second) {
                dist[it->first] = dist[tn] + it->second;
                if(inq[it->first] == 0) {
                    if(++cnt[it->first] >= n+1) {
                        queue<int> nq;
                        nq.push(it->first);
                        neg[it->first] = 1;
                        while(!nq.empty()) {
                            int tn = nq.front();
                            nq.pop();
                            dist[tn] = -0xfffffff;
                            for(vector<pair<int, int> >::iterator it = g[tn].begin();
                                it != g[tn].end(); it++) {
                                if(neg[it->first] == 0) {
                                    neg[it->first] = 1;
                                    nq.push(it->first);
                                }
                            }
                        }
                    }
                    if(neg[it->first] == 0) {
                        Q.push(it->first);
                        inq[it->first] = 1;
                    }
                }
            }
        }
    }
}
int main() {
    int m, C[205];
    int i, j, x, y;
    int cases = 0;
    while(scanf("%d", &n) == 1) {
        for(i = 1; i <= n; i++) {
            scanf("%d", &C[i]);
            dist[i] = 0xfffffff;
            g[i].clear();
        }
        scanf("%d", &m);
        while(m--) {
            scanf("%d %d", &x, &y);
            g[x].push_back(make_pair(y, (C[y]-C[x])*(C[y]-C[x])*(C[y]-C[x])));
        }
        scanf("%d", &m);
        spfa(1);
        printf("Set #%d\n", ++cases);
        while(m--) {
            scanf("%d", &x);
            if(x <= 0 || x > n || dist[x] < 3 || dist[x] == 0xfffffff)
                puts("?");
            else
                printf("%d\n", dist[x]);
        }
    }
    return 0;
}
/*
5 6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
*/