PTA最短路径算法R6-1

PTA最短路径算法R6-1是一道题目，需要使用Dijkstra算法求解。具体题目描述如下：

给定一个有向带权图，节点从0到n-1编号，求0号节点到n-1号节点的最短路径长度，如果无法从0号节点走到n-1号节点，输出-1。

输入格式：
第一行包含整数n和m，表示图中节点个数和边数。
接下来m行每行包含三个整数x，y，z，表示存在一条从节点x到节点y的有向边，边长为z。

输出格式：
输出一个整数，表示从0号节点到n-1号节点的最短路径长度。如果路径不存在，则输出-1。

算法步骤如下：

1. 初始化：将0号节点到各个节点的距离数组dist初始化为无穷大，dist[0]=0。

2. Dijkstra算法：从所有未确定最短路径的节点中，选取dist值最小的节点u，将其标记为已确定最短路径。然后遍历所有从节点u出发的边，更新其它节点的dist值。若更新后的dist值比原来的小，则更新dist值。

3. 重复执行步骤2，直到所有节点的dist值都已确定最短路径或者不存在0号节点到n-1号节点的路径。

4. 输出结果：若存在0号节点到n-1号节点的路径，输出dist[n-1]，否则输出-1。

具体实现细节见下面的代码示例：

相关问题

pta最短路径迪杰斯特拉算法程序填空

以下是PTA最短路径迪杰斯特拉算法程序的填空代码：

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 501
#define INFINITY 65535

typedef int Vertex;
typedef int WeightType;
typedef char DataType;

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;
    int Ne;
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum];
};
typedef PtrToGNode MGraph;

typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;
    WeightType Weight;
};
typedef PtrToENode Edge;

MGraph CreateGraph( int VertexNum )
{
    Vertex V, W;
    MGraph Graph;

    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    for (V=0; V<Graph->Nv; V++)
        for (W=0; W<Graph->Nv; W++)
            Graph->G[V][W] = INFINITY;

    return Graph;
}

void InsertEdge( MGraph Graph, Edge E )
{
    Graph->G[E->V1][E->V2] = E->Weight;
    Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    int Nv, i;

    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);

    scanf("%d", &(Graph->Ne));
    if ( Graph->Ne != 0 ) {
        E = (Edge)malloc(sizeof(struct ENode));
        for (i=0; i<Graph->Ne; i++) {
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            E->V1--;
            E->V2--;
            InsertEdge( Graph, E );
        }
    }

    return Graph;
}

void PrintDist( WeightType dist[], int N )
{
    int i;
    for ( i=0; i<N; i++ )
        printf("%d ", dist[i]);
}

void PrintPath( int path[], int V )
{
    if ( path[V] != -1 ) {
        PrintPath( path, path[V] );
        printf(" %d", V);
    } else
        printf("%d", V);
}

void Dijkstra( MGraph Graph, WeightType dist[], int path[], Vertex S )
{
    int collected[MaxVertexNum];
    Vertex V, W, MinV;
    WeightType MinDist;

    for ( V=0; V<Graph->Nv; V++ ) {
        dist[V] = Graph->G[S][V];
        if ( dist[V]<INFINITY )
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = 0;
    }
    dist[S] = 0;
    collected[S] = 1;

    while (1) {
        MinDist = INFINITY;
        MinV = -1;
        for ( V=0; V<Graph->Nv; V++ ) {
            if ( collected[V]==0 && dist[V]<MinDist ) {
                MinDist = dist[V];
                MinV = V;
            }
        }
        if (MinV==-1) break;
        collected[MinV] = 1;
        for( W=0; W<Graph->Nv; W++ ) {
            if ( collected[W]==0 && Graph->G[MinV][W]<INFINITY ) {
                if ( Graph->G[MinV][W]<0 ) {
                    printf("Error: Negative Dist!\n");
                    return;
                }
                if ( dist[MinV]+Graph->G[MinV][W] < dist[W] ) {
                    dist[W] = dist[MinV]+Graph->G[MinV][W];
                    path[W] = MinV;
                }
            }
        }
    }
}

int main()
{
    int i;
    WeightType dist[MaxVertexNum];
    int path[MaxVertexNum];
    MGraph G = BuildGraph();

    Vertex S = 0;
    Dijkstra( G, dist, path, S );

    for ( i=1; i<G->Nv; i++ ) {
        printf("%d\n", dist[i]);
    }

    return 0;
}

pta r6-1 简单选择排序

简单选择排序是一种基于交换的排序算法，它的基本思想是：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完为止。

具体的实现步骤如下：

1. 在待排序的元素中，选择最小的元素作为首元素，将其与序列中第一个元素进行交换；
2. 从剩余的元素中选择最小的元素作为次首元素，将其与序列中第二个元素进行交换；
3. 重复上述步骤，直到将整个序列排完为止。

下面是简单选择排序的C++代码实现：

void selectSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;   // 最小元素的下标
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;   // 更新最小元素的下标
            }
        }
        if (minIndex != i) {
            swap(a[i], a[minIndex]);    // 交换最小元素和当前元素
        }
    }
}