图论入门 dijkstra（邻接矩阵）

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;

int main()
{
	int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,min;
	scanf("%d%d",&n,&m); //图的规模 n顶点个数 m边的个数
	//图的初始化
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		if(i==j) e[i][j]=0;
		else e[i][j]=inf;
	}
	//读入边
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&t1,&t2,&t3);
		e[t1][t2]=t3;
	}
	//初始化dis：起点到相邻点的权值  (假设起点是1)  book
	int s=1;
	for(i=1;i<=n;i++)
	{
		if(i==s)
			dis[i]=0;
		dis[i]=e[s][i];
		book[i]=0;
	}
	book[s]=1;
	//dijkstra核心算法
	for(i=1;i<=n-1;i++)
	{
		min=inf;
		for(j=1;j<=n;j++)  //找到离当前点最近的点
		{
			if(min>dis[j] && book[j]==0)
			{
				min=dis[j];
				u=j;
			}
		}
		book[u]=1;  //下次把这个点当起点
		for(j=1;j<=n;j++)  //松弛  把u当做中转站  看看有没有能优化距离的
		{
			if(e[u][j]<inf && dis[j]>dis[u]+e[u][j])
			{
				dis[j]=dis[u]+e[u][j];
			}
		}
	}
	//output
	for(i=1;i<=n;i++)
	{
		printf("%d ",dis[i]);
	}
	printf("\n");
	return 0;
}