dijkstra

gistfile1.hpp

#include <cstdio>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

#define MAXN 100005
#define INF 100000000

struct PATH {
    int b,dist;

    PATH ( int _b = 0, int _dist = 0 ) : b(_b),dist(_dist) {}

    };

int n,m,A,B,dist[MAXN],ca,cb,len;
vector <PATH> path[MAXN] ;

struct cmp {
    bool operator () ( const int &a, const int &b ){
        if ( dist[a] != dist[b] ) return dist[a] < dist[b];
        return a < b;
        }
    };

set < int, cmp > S;

int dijkstra ( int x, int y ){
    S.insert ( x );

    while ( !S.empty() ){
        x = *S.begin();
        S.erase ( S.begin() );

        if ( x == y ) return dist[y];

        for ( int i=0;i<path[x].size();++i )
            if ( dist[path[x][i].b] > dist[x] + path[x][i].dist ){
                S.erase ( path[x][i].b );
                dist[path[x][i].b] = dist[x] + path[x][i].dist;
                S.insert ( path[x][i].b );
                }

        }
    return -1;

    }

int main(){
    scanf("%d %d %d %d",&n,&m,&A,&B);
    for ( int i=0;i<m;++i ){
        scanf("%d %d %d",&ca,&cb,&len);
        path[ca].push_back ( PATH (cb,len) );
        path[cb].push_back ( PATH (ca,len) );
        }
    for ( int i=0;i<=n;++i )
        dist[i] = INF;
    dist[A] = 0;
    printf("%d\n",dijkstra ( A,B ));

    return 0;
    }