Dijkstra

spoj :

Easy Dijkstra Problem

Problem code: EZDIJKST

solution 1

( faster )

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;

#define INF 1000000;

struct edge {

int u;

int w;

};

bool operator <( edge a, edge b ) {

return a.w < b.w;

}

void dijkstra( vector< edge > graph[], int dist[], int N, int s ) {

dist[ s ] = 0;

priority_queue< edge > q;

q.push( ( edge ) { s, 0 } );

while ( !q.empty() ) {

edge p = q.top();

q.pop();

for ( int i = 0; i < graph[ p.u ].size(); ++i ) {

int u = p.u;

int v = graph[ p.u ][ i ].u;

if ( dist[ u ] + graph[ p.u ][ i ].w < dist[ v ] ) {

dist[ v ] = dist[ u ] + graph[ p.u ][ i ].w;

q.push( graph[ p.u ][ i ] );

}

}

}

}

int main() {

int t;

int N, E;

int S, T;

int u, v, w, i;

scanf( "%d", &t );

while ( t > 0 ) {

scanf( "%d%d", &N, &E );

vector< edge > graph[ N + 1 ];

int dist[ N + 1 ];

for ( i = 0; i < E; ++i ) {

scanf( "%d%d%d", &u, &v, &w );

graph[ u ].push_back( ( edge ) { v, w } );

}

for ( i = 0; i <= N; ++i ) {

dist[ i ] = INF;

}

scanf( "%d%d", &S, &T );

dijkstra( graph, dist, N, S );

if ( dist[ T ] != 1000000 ) {

printf( "%d\n", dist[ T ] );

}

else {

printf( "NO\n" );

}

--t;

}

return 0;

}

solution 2

#include <stdio.h>

#include <limits.h>

int a[1501][1501];

//int v[1500];

int oo;

int mind(int d[],int v[],int nv)

{

 int mini=INT_MAX,m;

 //printf("the value of nv is %d\n",nv);

 for(int i=1;i<=nv;i++)

 {  //printf("we are in loop\n");

     if(!v[i] && d[i]<mini)

        mini=d[i],m=i;

 }

// printf("minimum distance is of %dand index is %d\n",mini,m);

 return m;

}

int dj(int src,int tv)

{

    int v[1500],d[1500];// for keeping the finalization info and keeping the distanvle info

    for(int i=0;i<=tv;i++)

    {

        v[i]=0,d[i]=INT_MAX;

    }

    d[src]=0;

    for(int c=0;c<tv-1;c++)

    {

        int u=mind(d,v,tv);//sending the distance and the vertices array

       // printf("here it comes to dj");

        v[u]=1;

        /*if(u==2)

            break;*/

        for(int i=1;i<=tv;i++)

        {

            if(v[i]==0 && a[u][i] && d[u]!=INT_MAX && a[u][i]+d[u]<d[i]){

            // printf("\n************** it has updated a element %d with value %d*************\n",i,a[u][i]+d[u]);

                d[i]=a[u][i]+d[u];}

        }

    }

    if(d[oo]!=INT_MAX)

    printf("%d\n",d[oo]);

    else

    printf("NO\n");

}

int main()

{

int RKS=INT_MAX;

// printf("%d",RKS);

    int t,v,e,u,r,w,i,j;

    scanf("%d",&t);

    while(t--){for(i=0;i<1000;++i)

            for(j=0;j<1000;j++)

            a[i][j]=0;

    scanf("%d %d",&v,&e);

    for(int l=0;l<e;l++)

    {

        scanf("%d %d %d",&u,&r,&w);      a[u][r]=w;

    }

    //printf("it has scnanned all elements properly\n");

    int er ,fg;

    scanf("%d %d",&er,&fg);

    oo=fg;

    dj(er,v);

    }

    return 0;

}