test djikstra

gistfile1.txt

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <queue>
#include <stack>


using namespace std;


const int w = 1000;
const int MAX = 10000000;
int weights[w][w];


int minim(int a, int b) {
	return a < b ? a : b;
}

int djikstra(int s, int e, int n){
	queue<int> x;
	int optimal[w];
	for (int j = 0; j < n; j++)
		optimal[j] = MAX;
	optimal[s] = 0;

	x.push(s);

	bool visited[w];

	for (int i = 0; i < n; i++)
		visited[i] = 0;

	while (x.size()>0){
		int source = x.front();
		visited[source] = 1;
		x.pop();
		for (int j = 0; j < n; j++){
			int neighbourWeight = weights[source][j];
			if (neighbourWeight != -1 && !visited[j] && neighbourWeight != 0){
				optimal[j] = minim(optimal[j], optimal[source] + neighbourWeight);
			}
		}
		int minind = -1, minval = 1000000;

		for (int i = 0; i < n; i++){
			if (!visited[i]){
				if (optimal[i] < minval){
					minval = optimal[i];
					minind = i;
				}
			}
		}
		if (minind != -1)
			x.push(minind);
	}
	return optimal[e];
}

int _tmain()
{
	int n;
	cin >> n; // <= 1000

	int m[4][4];
	m[0][0] = 0;
	m[0][1] = 4;
	m[0][2] = 3;
	m[0][3] = -1;
	m[1][0] = 4;
	m[1][1] = 0;
	m[1][2] = -1;
	m[1][3] = 2;
	m[2][0] = 3;
	m[2][1] = -1;
	m[2][2] = 0;
	m[2][3] = 5;
	m[3][0] = -1;
	m[3][1] = 2;
	m[3][2] = 5;
	m[3][3] = 0;

	/*for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
		cout << "Enter weight between vertex " << i << " and vertex " << j << " :";
		cin >> weights[i][j];
		cout << endl;
		}
		}*/
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 4; j++){
			weights[i][j] = m[i][j];
		}
	}
	int s, e;
	cin >> s >> e;
	int ans = djikstra(s, e, n);
	cout << ans << endl;
	return 0;
}