测试题目 NKOJ1107 达喀尔拉力赛
方法一 Bellman-Ford. 计算 S 到任意点的最短路得到 dis[i], 计算任意点到 T 的最短路 sid[i], 枚举每一条边，假设这条边从 x 到 y, 权值 w.
显然次短路长度就是 min{ dis[x] + w + sid[y] } .这个方法代码非常好写，也很好想，不过跑了两次最短路，常数略大。
方法二 Dijkstra. dis 表示最短路, dis2 表示次短路, 见代码.
1 void Dijkstra(int beg) 2 { 3 LL i; 4 for (i = 1; i <= n; ++i) dis[i] = dis2[i] = INF; 5 dis[beg] = 0;//注意这里不能写 dis2[beg] = 0，想一想为什么（笑 6 while (!Q.empty()) Q.pop(); 7 Q.push(strdis(beg, dis[beg])); 8 while (!Q.empty()) { 9 strdis p = Q.top(); Q.pop();10 if (p.dis > dis2[p.v]) continue;////注意这里是 p.dis ，不能写 dis[p.v] ，因为当前取出的 p.dis 表示的也可能是 dis2[p.v] ，这与最短路写法中 p.dis 等价于 dis[p.v] 不同 11 for (i = 0; i < G[p.v].size(); ++i) {12 LL tmp = p.dis + G[p.v][i].w;//注意这里是 p.dis ，不能写 dis[p.v] ，因为当前取出的 p.dis 表示的也可能是 dis2[p.v] ，这与最短路写法中 p.dis 等价于 dis[p.v] 不同 13 if (dis[G[p.v][i].v] > tmp) {14 swap(dis[G[p.v][i].v], tmp);//注意这里最短路更新后，原来的值应该交换到 tmp 中，用于下面的 if 语句里更新次短路15 Q.push(strdis(G[p.v][i].v, dis[G[p.v][i].v]));16 }17 if (dis[G[p.v][i].v] < tmp && dis2[G[p.v][i].v] > tmp) { 18 dis2[G[p.v][i].v] = tmp;19 Q.push(strdis(G[p.v][i].v, dis2[G[p.v][i].v]));//注意 dis2 也应当 push 进队列，例子如下20 //例子：dis[5] = 100, dis2[5] = 20021 //有一条边 5 到 8 的边权值为 5022 //如果不把 dis2 入队，那么之后的算法中 dis[8] = 150, dis2[8] = INF23 //只有当队列里有 200 这个值，才能 200+50 得出 250，然后更新 dis2[8] = 250 24 }25 }26 }27 return ;28 } 完整代码：
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 typedef long long LL; 8 9 const int _N = 600;10 const long long INF = 99999999999999LL;11 12 LL n, m;13 LL dis[_N], dis2[_N];14 15 struct node {16 LL v, w;17 node(const LL &_v, const LL &_w):18 v(_v), w(_w) {}19 };20 21 struct strdis {22 LL v, dis;23 strdis(const LL &_v, const LL &_dis):24 v(_v), dis(_dis) {}25 bool operator < (const strdis &tmp) const26 {27 return this->dis > tmp.dis;28 }29 };30 31 vector G[_N];32 priority_queue Q;33 34 void Dijkstra(int beg)35 {36 LL i;37 for (i = 1; i <= n; ++i) dis[i] = dis2[i] = INF;38 dis[beg] = 0;//注意这里不能写 dis2[beg] = 0，想一想为什么（笑 39 while (!Q.empty()) Q.pop();40 Q.push(strdis(beg, dis[beg]));41 while (!Q.empty()) {42 strdis p = Q.top(); Q.pop();43 if (p.dis > dis2[p.v]) continue;////注意这里是 p.dis ，不能写 dis[p.v] ，因为当前取出的 p.dis 表示的也可能是 dis2[p.v] ，这与最短路写法中 p.dis 等价于 dis[p.v] 不同 44 for (i = 0; i < G[p.v].size(); ++i) {45 LL tmp = p.dis + G[p.v][i].w;//注意这里是 p.dis ，不能写 dis[p.v] ，因为当前取出的 p.dis 表示的也可能是 dis2[p.v] ，这与最短路写法中 p.dis 等价于 dis[p.v] 不同 46 if (dis[G[p.v][i].v] > tmp) {47 swap(dis[G[p.v][i].v], tmp);//注意这里最短路更新后，原来的值应该交换到 tmp 中，用于下面的 if 语句里更新次短路48 Q.push(strdis(G[p.v][i].v, dis[G[p.v][i].v]));49 }50 if (dis[G[p.v][i].v] < tmp && dis2[G[p.v][i].v] > tmp) { 51 dis2[G[p.v][i].v] = tmp;52 Q.push(strdis(G[p.v][i].v, dis2[G[p.v][i].v]));//注意 dis2 也应当 push 进队列，例子如下53 //例子：dis[5] = 100, dis2[5] = 20054 //有一条边 5 到 8 的边权值为 5055 //如果不把 dis2 入队，那么之后的算法中 dis[8] = 150, dis2[8] = INF56 //只有当队列里有 200 这个值，才能 200+50 得出 250，然后更新 dis2[8] = 250 57 }58 }59 }60 return ;61 }62 63 int main()64 {65 LL i, t1, t2, t3;66 scanf("%lld%lld", &n, &m);67 for (i = 1; i <= m; ++i) {68 scanf("%lld%lld%lld", &t1, &t2, &t3);69 G[t1].push_back(node(t2, t3));70 G[t2].push_back(node(t1, t3));71 }72 Dijkstra(1);73 printf("%lld\n", dis2[n]);74 return 0;75 }