CFR 20 C. Dijkstra? ( Dijkstra )

Problem - 20C - Codeforces
根本裸題。。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXW = 1e6 + 6;
typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, int > pli;

int n, m;
vector< pii > G[ MAXN ];

struct Dijkstra{
    ll dis[ MAXN ];
    int prev[ MAXN ];
    void solve(){
        fill( dis, dis + MAXN, 1LL << 60 );
        memset( prev, -1, sizeof(prev) );
        priority_queue< pli, vector< pli >, greater< pli > > pq;
        pq.push( pli( dis[ 1 ] = 0, 1 ) );
        while( !pq.empty() ){
            ll d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            for( pii &p : G[ u ] ){
                int v = p.first;
                int w = p.second;
                if( dis[ v ] > dis[ u ] + w )
                    dis[ v ] = dis[ u ] + w,
                    prev[ v ] = u,
                    pq.push( pli( dis[ v ], v ) );
            }
        }
    }
    void printPath(){
        if( dis[ n ] == 1LL << 60 ) return (void)puts("-1");
        stack< int > stk;
        for( int u = n; u != -1; u = prev[ u ] )
            stk.push( u );
        for( ; !stk.empty(); stk.pop() )
            printf("%d%c", stk.top(), stk.size() == 1 ? '\n' : ' ');
    }
} sp;

void solve(){
    sp.solve();
    sp.printPath();
}

int main(){
    ios::sync_with_stdio( false );
    cin >> n >> m;
    for( int i = 0; i < m; ++i ){
        int u, v, w; cin >> u >> v >> w;
        G[ u ].push_back( pii( v, w ) );
        G[ v ].push_back( pii( u, w ) );
    }
    solve();
    return 0;
}