[a462] Beats of the Angel
內容 ：
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
提示 ：
出處 ：
很明顯的, 必須先找到一條最短路徑,
那首先我們會發現只有在最短路徑上的邊上的權值做改變時, 天使才會往更長的方向走,
只要在"其中一條"最短路徑邊上枚舉即可,
因為只可能多條最短路徑上的交集, 因此枚舉一條也會算到交集
#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;
}