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

49愛的鼓勵 6訂閱站台

AB國是一個非常不一樣的國家，在這個國家裡面的人民，他們沒有壽命限制、受傷再嚴重只要時間夠久也能夠恢復、甚至當身體灰飛煙滅後，人民也能從某個固定點復活，彷彿線上遊戲般砍掉也能重練。但也如線上遊戲般，大部分的人民沒有自主意識，有如NPC般遵守規律的作息，只有少部分的人才能隨自我意志來行動。

因為人們長生不死，偶而還會伴隨著新同伴的加入（原因不明，推測是在固定復活點處隨機產生，只是產生出來的人大部分都是NPC），這群人無所事事便想搞破壞（因為根本不會死），於是AB國在創建初期是毫無秩序的，直到「天使」現身。

「天使」是依照旨意下來管理AB國的人民（也就是從重生點出生），能力強大，若是有不遵守規矩的人民，他都能以最快的速度找到並制伏，最高紀錄曾經一天引發數次 Legendary ，可謂極其兇惡。

於是原來具有自主意識的人們（又復活了）開始團結起來，名為「英雄戰線聯盟」，為了恢復昔日的自由，與天使互相對抗。

在一次的戰役中，「戰線聯盟」發現天使出現在一處基地的前方不遠處，而那個基地正巧在進行著重要的會議，主要的領導都在裡面商討戰略，無法現身抵抗天使，因此在基地外守衛的你，必須盡快想出辦法，拖延到最多的時間，並祈禱內部的會議能盡早結束。

於是在來到AB國之前的你，回憶起曾經修過的程式設計，開始假想基地周圍有 N 處空地，空地之間總共會有M個通道相連，當天使在空地時，因為周圍沒有障礙物，可以展開能力到達這個空地的任意地方，但如果要在空地間移動，必須經由空地之間的通道，在此補充一下，有些人可能認為的的文章有Bug，認為前面我提到了「天使的能力強大」，為何不直接飛進基地就好了呢？理由如下：天使雖然強大，但他的能力最為優秀的只有兩項，一是戰技出眾，二是gank極強（這導因於他有內建GPS，等等這項能力也會有些用處），因而能殺爆全場。

扯回重點，因為每個通道的環境都不太相同，因此天使在通過通道時，會需要消耗一些時間，或多或少，天使當然也知道這回事，趕緊啟動腦內GPS，企圖以最短時間攻入基地。

當然天使的能力在「戰線聯盟」並不是秘密，於是聰明的你，拿起了手上的武器（電腦），也去試著攻擊其中一個通道，讓天使在通過這個通道時，所需時間加倍（你手上只有一台電腦，因此只能攻擊一個通道），當通道通過的時間改變後，天使將會重新計算新的最短通過時間，你的目的就是要讓他後來通過的時間，與原來通過的時間相比，延長時間相差最長。

（後記：雖然大家都及時趕出來對抗天使，但依舊被殺到Legendary滿天飛……）

 

輸入有多筆測資。

每筆測資第一行有兩正整數 N（1 <= N <= 1000）、M（1 <= M <= 100000），如題幹所述。此時，空地的編號為 1 ~ N，天使的初始位置在 1，基地在 N 。接著M行，每行有三個正整數 a、b（1 <= a, b <= N）、w（1 <= w <= 10000000），代表空地 a 和空地 b 之間有條通道，通過這條通道的時間為 w。

 

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

2

板橋高中練習題 (管理：m80126colin)

---

很明顯的, 必須先找到一條最短路徑,
那首先我們會發現只有在最短路徑上的邊上的權值做改變時, 天使才會往更長的方向走,
只要在"其中一條"最短路徑邊上枚舉即可,
因為只可能多條最短路徑上的交集, 因此枚舉一條也會算到交集

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
struct Arc {
    int to, v;
};
typedef vector<Arc>::iterator it;
vector<Arc> nlist[1001];
int dis[1001], dis2[1001];
int used[1001], used2[1001];
int ans = 0;
int spfa2(int, int);
void spfa(int st, int ed) {
    memset(dis, 63, sizeof(dis));
    memset(used, 0, sizeof(used));
    dis[st] = 0;
    queue<int> Q;
    Q.push(st);
    int tn;
    while(!Q.empty()) {
        tn = Q.front();
        used[tn] = 0;
        Q.pop();
        for(it i = nlist[tn].begin(); i != nlist[tn].end(); i++) {
            if(dis[i->to] > dis[tn] + i->v) {
                dis[i->to] = dis[tn] + i->v;
                if(used[i->to] == 0) {
                    used[i->to] = 1;
                    Q.push(i->to);
                }
            }
        }
    }
    Q.push(ed);
    int spath = dis[ed];
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(it i = nlist[tn].begin(), j; i != nlist[tn].end(); i++) {
            if(dis[tn] - i->v == dis[i->to]) {
                Q.push(i->to);
                for(j = nlist[i->to].begin(); j != nlist[i->to].end(); j++) {
                    if(j->to == tn && j->v == i->v) {
                        break;
                    }
                }
                if(i->v <= ans)
                    break;
                i->v <<= 1;
                j->v <<= 1;
                int tpath = spfa2(st, ed);
                if(tpath - spath > ans)
                    ans = tpath - spath;
                i->v >>= 1;
                j->v >>= 1;
                break;
            }
        }
    }
}
int spfa2(int st, int ed) {
    memset(dis2, 63, sizeof(dis2));
    memset(used2, 0, sizeof(used2));
    dis2[st] = 0;
    queue<int> Q2;
    Q2.push(st);
    int tn;
    while(!Q2.empty()) {
        tn = Q2.front();
        used2[tn] = 0;
        Q2.pop();
        for(it i = nlist[tn].begin(); i != nlist[tn].end(); i++) {
            if(dis2[i->to] > dis2[tn] + i->v) {
                dis2[i->to] = dis2[tn] + i->v;
                if(used2[i->to] == 0) {
                    used2[i->to] = 1;
                    Q2.push(i->to);
                }
            }
        }
    }
    return dis2[ed];
}
int main() {
    int n, m, i, a, b, w;
    while(scanf("%d %d", &n, &m) == 2) {
        for(i = 1; i <= n; i++)
            nlist[i].clear();
        Arc tmp;
        for(i = 0; i < m; i++) {
            scanf("%d %d %d", &a, &b, &w);
            tmp.to = b, tmp.v = w;
            nlist[a].push_back(tmp);
            tmp.to = a;
            nlist[b].push_back(tmp);
        }
        ans = 0;
        spfa(1, n);
        printf("%d\n", ans);
    }
    return 0;
}