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