#include <iostream>
#include<stdio.h>
#include<time.h>
#define n 6
int xmin(int p[][n], int i);
int c[n] = { 0 };
int d[2][n] = { 0 };
int main()
{
	int a[n][n] = { 0,6,3,1000,1000,1000,6,0,2,5,1000,1000,3,2,0,3,4,1000,1000,5,3,0,2,3,1000,1000,4,2,0,5,1000,1000,1000,3,5,0 };
	int i, j, min = 0, s = 0, nn = 0;
	for (i = 0; i < n; i++)
		d[0][i] = a[0][i];
	c[0] = 0;
	for (i = 0; i < n;)
	{
		for (j = i + 1; j < n; j++)
			if (d[0][j] > (d[0][c[i]] + a[c[i]][j]))
			{
				d[0][j] = d[0][c[i]] + a[c[i]][j];
				d[1][j] = 1;
			}
		s = c[i];
		c[i += 1] = xmin(d, s);
		nn += 1;
		if ((c[i] == n - 1) && d[1][j]==0)
		{
			c[i - 1] = c[i];
			nn -= 1;
		}
		if (c[i] == n - 1)
			break;
	}
	printf("路径为：");
	for (i = 0; i <= nn; i++)
	{
		printf("%d", c[i]);
		if (i < nn)
			printf("-->");
	}
	printf("\n最短路径为：");
	printf("%d\n", d[0][n-1]);
	return 0;
}
int xmin(int p[][n], int i)
{
	int j, min = i+1;
	for (j = i+1; j < n; j++)
		if (p[0][j] < p[0][min])
			min = j;
	return min;
}