[BZOJ1726][Usaco2006 Nov]Roadblocks第二短路

1726: [Usaco2006 Nov]Roadblocks第二短路

Time Limit: 5 Sec??Memory Limit: 64 MB Submit: 1277??Solved: 607 [Submit][Status][Discuss]

Description

貝茜把家搬到了一個小農場，但她常常回到FJ的農場去拜訪她的朋友。貝茜很喜歡路邊的風景，不想那么快地結束她的旅途，于是她每次回農場，都會選擇第二短的路徑，而不象我們所習慣的那樣，選擇最短路。 貝茜所在的鄉村有R(1<=R<=100,000)條雙向道路，每條路都聯結了所有的N(1<=N<=5000)個農場中的某兩個。貝茜居住在農場1，她的朋友們居住在農場N（即貝茜每次旅行的目的地）。 貝茜選擇的第二短的路徑中，可以包含任何一條在最短路中出現的道路，并且，一條路可以重復走多次。當然咯，第二短路的長度必須嚴格大于最短路（可能有多條）的長度，但它的長度必須不大于所有除最短路外的路徑的長度。

Input

* 第1行: 兩個整數，N和R，用空格隔開

* 第2..R+1行: 每行包含三個用空格隔開的整數A、B和D，表示存在一條長度為 D(1 <= D <= 5000)的路連接農場A和農場B

Output

* 第1行: 輸出一個整數，即從農場1到農場N的第二短路的長度

Sample Input

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output

450

輸出說明:

??? 最短路：1 -> 2 -> 4 (長度為100+200=300)
??? 第二短路：1 -> 2 -> 3 -> 4 (長度為100+250+100=450)

次短路模板題

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char buf[10000000], *ptr = buf - 1;
inline int readint(){int n = 0;char ch = *++ptr;while(ch < '0' || ch > '9') ch = *++ptr;while(ch <= '9' && ch >= '0'){n = (n << 1) + (n << 3) + ch - '0';ch = *++ptr;}return n;
}
const int maxn = 5000 + 10, maxm = 100000 + 10;
struct Edge{int to, val, next;Edge(){}Edge(int _t, int _v, int _n): to(_t), val(_v), next(_n){}
}e[maxm * 2]; 
int fir[maxn] = {0}, cnt = 0;
inline void ins(int u, int v, int w){e[++cnt] = Edge(v, w, fir[u]); fir[u] = cnt;e[++cnt] = Edge(u, w, fir[v]); fir[v] = cnt;
}struct Node{int dis, idx;Node(){}Node(int _d, int _i): dis(_d), idx(_i){}bool operator < (const Node &x) const {return dis > x.dis;}
}t;
priority_queue<Node> q;
int dis1[maxn], dis2[maxn];
void dijkstra(){memset(dis1, 0x3f, sizeof dis1);memset(dis2, 0x3f, sizeof dis2);dis1[1] = 0;q.push(Node(0, 1));int u, v, w;while(!q.empty()){t = q.top(); q.pop();u = t.idx;if(t.dis > dis2[u]) continue;for(int i = fir[u]; i; i = e[i].next){v = e[i].to;w = t.dis + e[i].val;if(dis1[v] > w){swap(dis1[v], w);q.push(Node(dis1[v], v));}if(dis1[v] < w && w < dis2[v]){dis2[v] = w;q.push(Node(dis2[v], v));}}}
}
int n, m;
int main(){fread(buf, sizeof(char), sizeof(buf), stdin); n = readint();m = readint();for(int u, v, w, i = 1; i <= m; i++){u = readint();v = readint();w = readint();ins(u, v, w);}dijkstra();printf("%d\n", dis2[n]);return 0;
}

?