迷宫(maze)

Description
　破了魔法阵后，亮亮进入了一座迷宫。这座迷宫叫做“梦境迷宫”，亮亮只有走出这座迷宫，才能从睡梦中醒来。

　梦境迷宫可以用无向图来表示。它共有 $ n $ 个点和 $ m $ 条双向道路，每条道路都有边权，表示通过这条道路所需的时间，且每条道路可以多次经过。亮亮位于一号点，而出口则是 $ n $ 号点。原本，亮亮该找到一条最短路，快速冲出迷宫，然而，梦境迷宫的特殊之处在于，如果沿着最短路到达出口，亮亮就会永远陷入梦境。因此，亮亮必须寻找一条次短路。次短路的长度须严格大于最短路（可以有多条）的长度，同时又不大于所有除最短路外的道路的长度。

　你的任务，就是编写一个程序，帮助亮亮找到通向出口的次短路。

Input
第一行有两个整数 $ n,m $，表示迷宫内共有 $ n $ 个点，$ m $ 条边。

接下来 $ m $ 行，每行三个整数 $ x,y,z $ 表示结点 $ x $ 和 $ y $ 之间连有一条边权为 $ z $ 的无向边。

Output
一个整数，表示次短路的长度。

这是某场我校模拟赛的T3,难得是这么水的一道T3,就是个次短路的板子题,但是我考场上就像失了智一样,没写出来…只好用一个不正确的贪心骗上30分走人

其实你每次更新最短路的同时就能把次短路顺便更新/记录了,只需要再开一个_dis数组来记录次短路就行了

更新的时候能更新最短路就更新最短路,否则次短路(最短路优先级还是比较高)

然后….然后就没了,注意一下细节就行了,哦,还有一点——

别忘了初始化！！！！！！

这个代码的原型是enceladus大佬的板子合集中的,我Copy之后和同学们探讨了一下,搞明白了就自己写了一个,因为先入为主,所以难免长得像 $QwQ$

Code:

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#define int long long
#define pri_queue std::priority_queue
#define pii std:: pair < int , int >
#define mp std:: make_pair
#define vec std::vector < pii >
#define gret std::greater < pii >

const int N = 1e6 + 5 ;

struct edge { int to , next , data ; } e[N] ;

int n , m , tot , head[N] ;
int dis[N] , _dis[N] ;
pri_queue < pii , vec , gret > q ;

inline void build ( int u , int v , int w ){
    e[++tot].next = head[u] ; e[tot].to = v ;
    e[tot].data = w ; head[u] = tot ; return;
}

template < typename T >
    inline void swap ( T & x , T & y ) { T t = x ; x = y ; y = t ; return ; }

inline void Dijkstra ( int cur ) {
    memset ( dis , 0x3f , sizeof ( dis ) ) ;
    memset ( _dis , 0x3f , sizeof ( _dis ) ) ;
    dis[cur] = 0 ; q.push ( mp ( dis[cur] , cur ) ) ;
    while ( ! q.empty ( ) ){
        pii tmp = q.top () ; q.pop () ;
        int j = tmp.second , val = tmp.first ;
        if ( _dis[j] < val ) continue ;
        for (int i = head[j] ; i ; i = e[i].next ){
            int k = e[i].to , dist = val + e[i].data ;
            if ( dis[k] > dist ){
                _dis[k] = dis[k] ;
                swap( dis[k] , dist ) ;
                q.push ( mp ( dis[k] , k ) ) ;
            }
            if ( _dis[k] > dist && dis[k] < dist ){
                _dis[k] = dist ;
                q.push ( mp( _dis[k] , k ) ) ;
            }
        }
    }
    return ;
}

signed main(){
    scanf ("%lld%lld" , & n , & m ) ;
    for (int i = 1 ; i <= m ; ++ i){
        register int u , v , w ;
        scanf ("%lld%lld%lld" , & u , & v , & w ) ;
        build ( u , v , w ) ; build ( v , u , w ) ;
    }
    Dijkstra ( 1 ) ; printf ("%lld\n" , _dis[n] ) ;
    system("pause") ; return 0 ;
}