单源最短路径(Dijkstra)O(n*n)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 1000000         //无穷大
#define MAXN 20             //顶点个数的最大值
int n;                      //顶点个数
int Edge[MAXN][MAXN];       //邻接矩阵
int S[MAXN];                //Dijkstra算法用到的三个数组
int dist[MAXN];
int path[MAXN];
void Dijkstra(int v0)
{
    int i,j,k;
    for(i = 0;i < n;i++){
        dist[i] = Edge[v0][i];
        S[i] = 0;
        if(i != v0&&dist[i] < INF) path[i] = v0;
        else path[i] = -1;
    }
    S[v0] = 1; dist[v0] = 0; //顶点v0加入到顶点集合S
    for(i = 0;i < n-1;i++){
        int min = INF, u = v0;
                //选择当前集合T中具有最短路径的顶点u
        for(j = 0;j < n;j++){
            if(!S[j]&&dist[j] < min){
                u = j; min = dist[j];
            }
        }
        S[u] = 1;           //将顶点u加入到集合S,表示它的最短路径已求得
        //修改T集合中顶点的dist和path数组元素值
        for(k = 0;k < n;k++){
            if(!S[k] && Edge[u][k] < INF&&dist[u]+Edge[u][k] < dist[k]){
                dist[k] = dist[u] + Edge[u][k];
                path[k] = u;
            }
        }
    }
}

int main()
{
    int i,j;
    int u,v,w;              //边的起点和终点及权值
    scanf("%d",&n);         //读入顶点个数n
    while(1){
        scanf("%d%d%d",&u,&v,&w);       //读入边的起点和终点
        if(u == -1&&v == -1&&w == -1) break;
        Edge[u][v] = w;                 //构造邻接矩阵
    }
    for(i = 0;i < n;i++){
        for(j = 0;j <  n;j++){
            if(i == j) Edge[i][j] == 0;
            else if(Edge[i][j] == 0) Edge[i][j] = INF;
        }
    }
    Dijkstra(0);            //求顶点0到其他顶点的最短路径
    int shortest[MAXN];      //输出最短路径上的各个顶点时存放各个顶点的序号
    for(i = 1;i < n;i++){
        printf("%d\t",dist[i]);     //输出顶点0到顶点i的最短路径长度
        //以下代码用于输出顶点0到顶点i的最短路径
        memset(shortest,0,sizeof(shortest));
        int k = 0;          //k表示shortest数组中最后一个元素的下标
        shortest[k] = i;
        while(path[shortest[k]] != 0){
            k++;
            shortest[k] = path[shortest[k-1]];
        }
        k++;
        shortest[k] = 0;
        for(j = k;j > 0;j--)
            printf("%d->",shortest[j]);
        printf("%d\n",shortest[0]);
    }
    return 0;
}
/**********示例
输入:
6
0 2 5
0 3 30
1 0 2
1 4 8
2 5 7
2 1 15
4 3 4
5 3 10
5 4 18
-1 -1 -1
输出:
20      0->2->1
5       0->2
22      0->2->5->3
28      0->2->1->4
12      0->2->5
***************/