The Dijkstra Algorithm for Single Source Shortest Path

Currently the code is still under development. This is just to have the track of docs that I'm using to write it
Theory : [ http://en.wikipedia.org/wiki/Dijkstra's_algorithm ]
Priority queue (STL) : [ http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html ]
[ http://www.technical-recipes.com/2011/priority-queues-and-min-priority-queues-in-c/ ]
Till now it feels like that's all you need, I don't know for sure though. Let's see
Update : Here's a full code of a problem that I solved using this algorithm [UVA 10986]

#include <iostream>
#include <list>
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

// based on TopCoder tutorial

#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define INF 200000010

list<ii> G[30000];

int djk( int s, int t, int n ) {
 vi D(n, INF);
 
 set<ii> q;
 D[s] = 0;
 q.insert(ii(0,s));
 
 while (!q.empty()) {
 
  
  ii top = *q.begin();
  q.erase(q.begin());
  int v = top.second, d = top.first;
  
  tr(G[v], it) {
   int v2 = it->second, cost = it->first;
   if (D[v2] > D[v] + cost) {
    if (D[v2] != INF) {
     q.erase(q.find(ii(D[v2],v2)));
    }
    D[v2] = D[v] + cost;
    q.insert(ii(D[v2],v2));
   }
   
  }
 }
 return D[t];
}


int main( void ) {
 int test, n, m, s, t, x, y, v, kase=1;
 scanf("%d",&test);
 while (test--) {
  scanf("%d %d %d %d",&n,&m,&s,&t);
  for (int i=0 ; i<=n ; i++) {
   G[i].clear();
  }
  for (int i=0 ; i<m ; i++) {
   scanf("%d %d %d",&x,&y,&v);
   G[x].push_back(ii(v,y));
   G[y].push_back(ii(v,x));
  }
  int res = djk(s,t,n);
  
  printf("Case #%d: ",kase++);
  if (res == INF) printf("unreachable\n");
  else printf("%d\n",res);
 } 
 
 return 0;
}

[C++] Bellman Ford Implementation

Bellman-Ford is a Single Source Shortest Path (SSSP) detection algorithm. I implemented this one using a new kind of approach to coding (new for me). I used a nested class implementation. The whole BFord algorithm is packed with it's data structure in an object. The edges are also implemented using an internal class in the object. I never did nested class before this. Looks awesome.

#include <cstdio>
#include <vector>

#define INF (1<<31 - 1)
#define NIL -1

using namespace std;

class bford {
  
public:
  
  class edge {
  public:
 int u, v, w;
  };
  
  int nVertex;
  int *d, *p;
  vector<edge> elist;
  
  bford( ) {
 d = new int[0];
 p = new int[0];
 elist.clear();
  }
  
  bool function( int s, int nVertex ) {
 
 d = new int[(const int)nVertex+1];
 p = new int[(const int)nVertex+1];
 
 int i, j, w, u, v;
 // init_single_source( s ) {
 for (i=0 ; i<=nVertex ; i++) {
  d[i] = INF;
  p[i] = NIL;
 }
 d[s] = 0;
 // }
 
 for (i=0 ; i<nVertex-1 ; i++) {
  for ( j=0 ; j<elist.size() ; j++) {
   // relax( elist[j].u, elist[j].v, elist[j].w ) {
   u = elist[j].u;
   v = elist[j].v;
   w = elist[j].w;
   
   if (d[v] > d[u]+w) {
    d[v] = d[u]+w;
    p[v] = u;
   }
   // }
  }
 }
 
 for (i=0 ; i<elist.size() ; i++) {
  if ( d[ elist[i].v ] > d[ elist[i].u ] + elist[i].w ) {
   return false;
  }
 }
 return true;
  }

};

int main( void ) {
  
  int i, u, v, w, nVertex, nEdge;
  
  bford grp;
  scanf("%d",&nVertex);
  
  scanf("%d",&nEdge);
  
  for (i=0 ; i<nEdge ; i++) {
 scanf("%d %d %d",&u,&v,&w);
 grp.elist.push_back(bford::edge{u,v,w});
  }
  
  printf("%s\n",(grp.function( 1, nVertex )?"True":"False"));
  
  for (i=1 ; i<=nVertex ; i++) {
 printf("%d - %d\n",i, grp.d[i]);
  }
  
  
  return 0;
  
}

[UVa] 374 - Big Mod

Used a recursive method from Art of Programming Contest

LL bigMod(LL b, LL p, LL m)
{
    if (!p) return 1;
    else if (!(p&0x01)) return power(bigMod(b,p/2,m),2)%m;
    else return (b%m * bigMod(b,p-1,m))%m;
}

#include <stdio.h>
#define LL long
LL power(LL a, LL p)
{
    int ret=1;
    while (p--)
        ret*=a;
    return ret;
}
LL bigMod(LL b, LL p, LL m)
{
    if (!p) return 1;
    else if (!(p&0x01)) return power(bigMod(b,p/2,m),2)%m;
    else return (b%m * bigMod(b,p-1,m))%m;
}

int main()
{
    LL b, p, m;
    while (scanf("%ld %ld %ld",&b,&p,&m)==3)
    {
       printf("%ld\n",bigMod(b,p,m));
    }
    return 0;
}