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

49愛的鼓勵 6訂閱站台

Problem E
Sending email
Time Limit: 3 seconds

"A new internet watchdog is creating a stir in Springfield. Mr. X, if that is his real name, has come up with a sensational scoop."

Kent Brockman

There are n SMTP servers connected by network cables. Each of the m cables connects two computers and has a certain latency measured in milliseconds required to send an email message. What is the shortest time required to send a message from server S to server T along a sequence of cables? Assume that there is no delay incurred at any of the servers.

Input
The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing n (2<=n<20000), m (0<=m<50000), S (0<=S<n) and T (0<=T<n). S!=T. The next m lines will each contain 3 integers: 2 different servers (in the range [0, n-1]) that are connected by a bidirectional cable and the latency, w, along this cable (0<=w<=10000).

Output
For each test case, output the line "Case #x:" followed by the number of milliseconds required to send a message from S to T. Print "unreachable" if there is no route from S to T.

Sample Input	Sample Output
3 2 1 0 1 0 1 100 3 3 2 0 0 1 100 0 2 200 1 2 50 2 0 0 1	Case #1: 100 Case #2: 150 Case #3: unreachable

---

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define oo 1000000000
using namespace std;
typedef struct {
    int to, v;
} Arc;
vector<Arc> myLink[20000];
void SPFA(int n, int st, int ed) {
    bool used[n];
    int dis[n];
    memset(used, 0, sizeof(used));
    for(int i = 0; i < n; i++)
        dis[i] = oo;
    queue<int> Q;
    Q.push(st);
    dis[st] = 0;
    int tv;
    while(!Q.empty()) {
        tv = Q.front();
        Q.pop();
        used[tv] = 0;
        for(vector<Arc>::iterator i = myLink[tv].begin(); i != myLink[tv].end(); i++) {
            if(dis[i->to] > dis[tv] + i->v) {
                dis[i->to] = dis[tv] + i->v;
                if(!used[i->to]) {
                    used[i->to] = true;
                    Q.push(i->to);
                }
            }
        }
    }
    if(dis[ed] == oo)
        puts("unreachable");
    else
        printf("%d\n", dis[ed]);
}
int main() {
    int N, Case = 0, i;
    int x, y, w, n, m, S, T;
    scanf("%d", &N);
    while(N--) {
        scanf("%d %d %d %d", &n, &m, &S, &T);
        for(i = 0; i < n; i++) {
            myLink[i].clear();
        }
        Arc tmp;
        while(m--) {
            scanf("%d %d %d", &x, &y, &tmp.v);
            tmp.to = y;
            myLink[x].push_back(tmp);
            tmp.to = x;
            myLink[y].push_back(tmp);
        }
        printf("Case #%d: ", ++Case);
        SPFA(n, S, T);
    }
    return 0;
}