#include <stdio.h>
#include <stdlib.h>
#include <sys/limits.h>

#define N 10

typedef struct {
	int l; /* длина */
	int v; /* вершина */
} r;

typedef struct {
	int n;
	int p; /* предыдущий */
	int d; /* расстояние */
	int m; /* помечена? */
	int nr; /* число ребёр */
	r *r;
} v;

struct initdata {
	int v1, l, v2;
} initdata[] = {
	/* from - len - to */
	{ 1, 4, 3 },
	{ 1, 5, 4 },
	{ 1, 8, 2 },
	{ 2, 6, 4 },
	{ 2, 8, 5 },
	{ 3, 3, 6 },
	{ 3, 3, 4 },
	{ 4, 9, 6 },
	{ 4, 2, 7 },
	{ 4, 5, 5 },
	{ 5, 6, 8 },
	{ 5, 5, 7 },
	{ 6, 1, 7 },
	{ 6, 3, 9 },
	{ 7, 7, 8 },
	{ 7, 7, 9 },
	{ 7, 4, 10 },
	{ 8, 4, 10 },
	{ 9, 2, 10 },
};

r*
init_r(int v, int *nr) {
	int i, j, k;
	r *r;

	for(i = 0, j = 0; i < sizeof(initdata)/sizeof(initdata[0]); i++)
		if ((initdata[i].v1 == v) || (initdata[i].v2 == v))
			j++;
	*nr = j;
	r = malloc(j*sizeof(r));

	for(i = 0, k = 0; i < sizeof(initdata)/sizeof(initdata[0]); i++) {
		if (initdata[i].v1 == v) {
			r[k].l = initdata[i].l;
			r[k].v = initdata[i].v2;
			k++;
		}
		if (initdata[i].v2 == v) {
			r[k].l = initdata[i].l;
			r[k].v = initdata[i].v1;
			k++;
		}
	}
	return r;
}

int mind(v *vv) {
	int i, m, nr;
	
	m = 9000;
	nr = -1;

	for(i = 0; i < N; i++) {
		if ((vv[i].d < m) && !vv[i].m) {
			m = vv[i].d;
			nr = i;
		}
	}
	return nr;
}


int dejkstra(v *vv, int from, int to) {
	int i, j, l, n;
	v *v;

	from--;
	vv[from].d = 0;
	for(;;) {
		n = mind(vv);
		if(n == -1)
			return;
		v = &vv[n];
		for(j = 0; j < v->nr; j++) {
			if (vv[v->r[j].v-1].d > v->d + v->r[j].l) {
				vv[v->r[j].v-1].d = v->d + v->r[j].l;
				vv[v->r[j].v-1].p = v->n;
			}
		}
		v->m = 1;
	}
}

int main() {
	v *vv;
	int i, j;

	vv = malloc(sizeof(v)*N);
	for(i = 0; i < N; i++) {
		vv[i].n = i+1;
		vv[i].d = 9000;
		vv[i].m = 0;
		vv[i].p = -1;
		vv[i].r = init_r(vv[i].n, &vv[i].nr);
	}
	for(i = 0; i < N; i++) {
		printf("(%d): D %d M %d\n", vv[i].n, vv[i].d, vv[i].m);
		for(j = 0; j < vv[i].nr; j++)
			printf("\tfrom %d to %d cost %d\n", vv[i].n, vv[i].r[j].v, vv[i].r[j].l);
	}
	dejkstra(vv, 2, 9);
	printf("pathes\n");
	for(i = 0; i < N; i++) {
		printf("(%d): %d\n", vv[i].n, vv[i].d);
	}
	printf("path: length: %d, ", vv[8].d);
	for(i = 9; i != -1; i = vv[i-1].p) {
		printf("%d->", i);
	}
	printf("\n");

}