Friday, 31 October 2014

Dijkstra

spoj :

Easy Dijkstra Problem

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;
}