--**
 * Dijkstra算法------------邻接矩阵实现
 * 时间复杂段O(n^2) 空间复杂段O(n^2)
 * 适用于n不大的题目
 */
const int MAXN = 1010;
const int INF = 999999999;

int n, k;
int map[MAXN][MAXN];
bool visit[MAXN];
int pre[MAXN];//记录路径
int dist[MAXN];//记录节点1到其他节点的最短路径值


void init()
{
    memset(visit, false, sizeof(visit));
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j)
            map[i][j] = INF;
        pre[i] = i;
        dist[i] = INF;
    }
}

--*
    Dijkstra算法 计算 节点1 -> 节点v的最短路径
    其中dist数组记录了节点1到各个节点的最短路径， pre数组记录了节点1到v最短路径的 沿途节点
    参数：目标
    无返回：dist[v]即为所求，如果dist[v] == INF说明找不到路径
*/
void Dijkstra(const int v)
{
    int i, j;
    int minValue, minNode;


    dist[1] = 0;
    visit[1] = true;

    for (i = 2; i <= n; ++i){
        if (map[1][i] != INF){
            dist[i] = map[1][i];
            pre[i] = 1;
        }
    }
    
    for (i = 1; i <= n; ++i){//本题这里的v换成n的话会超时， 一般v这个位置是矩阵的大小n 下面循环同理
        minValue = INF;
        minNode = 0;

        for (j = 1; j <= n; ++j){
            if (!visit[j] && minValue > dist[j]){
                minNode = j;
                minValue = dist[j];
            }
        }
        if (minNode == 0)
            break;

        visit[minNode] = true;
        for (j = 1; j <= n; ++j){
            if (!visit[j] && map[minNode][j] != INF && dist[j] > dist[minNode] + map[minNode][j]){
                dist[j] = dist[minNode] + map[minNode][j];
                pre[j] = minNode;
            }
        }

        if (minNode == v)//找到目标点
            break;
    }
    
}