Well, here we go:
the input generator:
Code:
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
const int NVERTEX = 8000;
const int NEDGE = 200000;
const int MAXWEIGHT = 1000;
const bool ISDIRECTED = false;
#define FILENAME "girdi.in"
bool isused[NVERTEX][NVERTEX];
int main() {
FILE *out = fopen(FILENAME,"w");
srand(time(NULL));
fprintf(out,"%d %d\n",NVERTEX,NEDGE);
for (int i=0; i<NEDGE; ) {
int v1,v2;
v1 = rand() % NVERTEX + 1;
v2 = rand() % NVERTEX + 1;
if (v1 != v2 && !isused[v1][v2]) {
isused[v1][v2] = true;
if (!ISDIRECTED) isused[v2][v1] = true;
int w = rand() % MAXWEIGHT + 1;
fprintf(out,"%d %d %d\n",v1,v2,w);
i++;
}
}
return 0;
}
the STL version:
Code:
#include <iostream>
#include <cstdio>
#include <set>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
//#define ii pair<int,int>
#define MAXV 8002
#define UNDIRECTED 1
#define MAX 0x7fffffff
int startv = 1, finalv = 0, nvertex, nedge;
using namespace std;
FILE *in,*out;
//ifstream in("girdi.in");
void dijkstra();
void read_file();
struct ii {
int first;
int second;
ii(int a,int b) { first = a,second = b; }
};
bool operator<(const ii &a, const ii &b) { return a.first < b.first || (a.first == b.first && a.second < b.second); }
vector<ii > m[MAXV];
int main() {
read_file();
clock_t start = clock(), end;
dijkstra();
end = clock();
printf("sure : %f\n",(float)(end-start)/CLOCKS_PER_SEC);
}
void read_file() {
in = fopen("girdi.in","r");
fscanf(in,"%d%d",&nvertex,&nedge);
finalv = nvertex;
for (int i=0; i<MAXV; i++) m[i].reserve(100);
for (int i=0; i<nedge; ++i) {
int v1,v2,w;
fscanf(in,"%d%d%d",&v1,&v2,&w);
m[v1].push_back(ii(v2,w));
if (UNDIRECTED) m[v2].push_back(ii(v1,w));
}
}
void dijkstra() {
set<ii > Q;set<ii >::iterator var;
int d[MAXV]; for (int i=0; i<MAXV; i++) d[i] = MAX;
d[startv] = 0;
Q.insert(ii(startv,d[startv]));
while (!Q.empty()) {
ii cur = *Q.begin();
Q.erase(Q.begin());
int v = cur.first;
for (vector<ii >::iterator it = m[v].begin(); it != m[v].end(); it++) {
int v2 = it->first, cost = it->second;
if (d[v2] > d[v] + cost) {
if (d[v2] != MAX) {
var = Q.find(ii(v2,d[v2]));
if (var != Q.end()) Q.erase(var);
}
d[v2] = d[v] + cost;
Q.insert(ii(v2,d[v2]));
}
}
}
printf("%d\n",d[finalv]);
}
and the heap version(this code does not belong to me. http://www.shygypsy.com/tools/ that's where i got it):
Code:
#include <string.h>
#define NN 8005
int graph[NN][NN], adj[NN][NN], deg[NN];
int d[NN], q[NN], inq[NN], prev[NN], qs;
#define CLR( x, v ) memset( x, v, sizeof( x ) )
#define BUBL { \
t = q[i]; q[i] = q[j]; q[j] = t; \
t = inq[q[i]]; inq[q[i]] = inq[q[j]]; inq[q[j]] = t; }
int dijkstra( int n, int s, int t )
{
CLR( d, 9 ); CLR( inq, -1 ); CLR( prev, -1 );
d[s] = qs = 0;
inq[q[qs++] = s] = 0;
prev[s] = -2;
while( qs )
{
// get the minimum from the q
int u = q[0]; inq[u] = -1;
// bubble down
q[0] = q[--qs];
if( qs ) inq[q[0]] = 0;
for( int i = 0, j = 2*i + 1, t; j < qs; i = j, j = 2*i + 1 )
{
if( j + 1 < qs && d[q[j + 1]] < d[q[j]] ) j++;
if( d[q[j]] >= d[q[i]] ) break;
BUBL;
}
// relax neighbours
for( int k = 0, v = adj[u][k]; k < deg[u]; v = adj[u][++k] )
{
int newd = d[u] + graph[u][v];
if( newd < d[v] )
{
d[v] = newd;
prev[v] = u;
if( inq[v] < 0 ) { inq[q[qs] = v] = qs; qs++; }
// bubble up
for( int i = inq[v], j = ( i - 1 )/2, t;
d[q[i]] < d[q[j]]; i = j, j = ( i - 1 )/2 )
BUBL;
}
}
}
return d[t];
}
//------- TESTING --------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
FILE *in=fopen("girdi.in","r");
int n, m;
while( fscanf(in, " %d %d\n", &n, &m ) == 2 )
{
memset( deg, 0, sizeof( deg ) );
while( m-- )
{
int u, v, w;
fscanf(in, " %d %d %d", &u, &v, &w );
graph[u][v] = graph[v][u] = w;
adj[u][deg[u]++] = v;
adj[v][deg[v]++] = u;
}
clock_t start = clock(), end;
int ans = dijkstra( n, 1, n );
end = clock();
printf("sure : %f\n",(float)(end-start)/CLOCKS_PER_SEC);
printf( "%d\n", ans );
}
//end = clock();
//printf("sure : %f\n",(float)(end-start)/CLOCKS_PER_SEC);
return 0;
}