题目描述
在带权有向图G中，给定一个源点v，求从v到G中的其余各顶点的最短路径问题，叫做单源点的最短路径问题。
在常用的单源点最短路径算法中，迪杰斯特拉算法是最为常用的一种，是一种按照路径长度递增的次序产生最短路径的算法。
可将迪杰斯特拉算法描述如下：
在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。
输入格式
输入的第一行包含2个正整数n和s，表示图中共有n个顶点，且源点为s。其中n不超过50，s小于n。
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。
输出
只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。
请注意行尾输出换行。
样例输入
4 1
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
样例输出
6 4 7
提示[-]
在本题中，需要按照题目描述中的算法完成迪杰斯特拉算法，并在计算最短路径的过程中将每个顶点是否可达记录下来，直到求出每个可达顶点的最短路径之后，算法才能够结束。
迪杰斯特拉算法的特点是按照路径长度递增的顺序，依次添加下一条长度最短的边，从而不断构造出相应顶点的最短路径。
另外需要注意的是，在本题中为了更方便的表示顶点间的不可达状态，可以使用一个十分大的值作为标记。
算法关键点：
1.若两顶点不可达，则将其设置为无穷大；若可达，则为权值。
2,源点的权值设为0。
3,将所有顶点分为两组，一组已经确定最短路径，即与源点为一个集合，另一组未确定路径，即剩下的全部顶点。
4,用Dist数组分别表示从源点到该顶点的最短路径长度。
5,进行N-1次循环，每次将一个顶点划分为和源点一组。
6,每次重新划分组后，将Dist数组逐个更新。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int const MAXLEN = 100;
const int INF = 1000000000;
int M[MAXLEN][MAXLEN];
int Dist[MAXLEN];
bool Visit[MAXLEN]={false};//标记是否确定路径
int N;//顶点数
int Start;//源点
void GetM()
{
cin>>N>>Start;
int temp;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cin>>temp;
if(temp==0) M[i][j]=INF;
else M[i][j]=temp;
}
}
}
void Init()
{
for(int i=0;i<N;i++)Dist[i]=M[Start][i];
Visit[Start]=true;
Dist[Start]=0;
}
void Dijkstra()
{
Init();
for(int i=0;i<N-1;i++)
{
int v;
int newdist=INF;
for(int j=0;j<N;j++)
{
if(!Visit[j] && Dist[j]<newdist)
{
v=j;
newdist=Dist[j];
}
}
Visit[v]=true;
for(int j=0;j<N;j++)
{
if(!Visit[j] && (Dist[v]+M[v][j])<Dist[j])
{
Dist[j]=Dist[v]+M[v][j];
}
}
}
}
void Print()
{
for(int i=0;i<N;i++)
{
if(i!=Start)
{
if(Dist[i]>=INF) cout<<"-1 ";
else cout<<Dist[i]<<" ";
}
}
cout<<endl;
}
int main()
{
freopen("D:\\test.txt","r",stdin);
freopen("D:\\tested.txt","w",stdout);
GetM();
Dijkstra();
Print();
return 0;
}