用c++解决下述问题：描述 After finishing the "Village Construction Project", the provincial government built more roads to make the trips between two villages more convenient. Then there is a new problem, which path is the shortest path between village V1 and V2? 输入 The first line of each test case contains four integers N, M, V1, V2 (1<=N, M, V1, V2<=1000; V1 != V2). Still, N and M represent the number of villages and the number of roads respectively. Then N lines follow, and every line contains three integers Ai, Bi, and Vi (1<=Ai, Bi <=N, Ai != Bi, 1<=Vi<=1000 ), meaning there is a road between village Ai and village Bi with its cost Vi. The inputs terminate at the end of the file (EOF). 输出 For each test case, output the cost of the shortest path between V1 and V2. If there is no path between V1 and V2, print -1. 输入样例 1

由于没有给出具体的输入样例，我就以一个例子为参考，假设输入样例为：

5 6 1 5 // N=5, M=6, V1=1, V2=5
1 2 2
1 3 3
2 3 1
2 4 5
3 5 4
4 5 1

则表示有5个村庄，6条道路，需要求解从村庄1到村庄5的最短路径。

下面是用 C++ 解决该问题的代码：

相关问题

用c++解决下述问题;描述 After finishing the "Village Construction Project", the provincial government built more roads to make the trips between two villages more convenient. Then there is a new problem, which path is the shortest path between village V1 and V2? 输入 The first line of each test case contains four integers N, M, V1, V2 (1<=N, M, V1, V2<=1000; V1 != V2). Still, N and M represent the number of villages and the number of roads respectively. Then N lines follow, and every line contains three integers Ai, Bi, and Vi (1<=Ai, Bi <=N, Ai != Bi, 1<=Vi<=1000 ), meaning there is a road between village Ai and village Bi with its cost Vi. The inputs terminate at the end of the file (EOF). 输出 For each test case, output the cost of the shortest path between V1 and V2. If there is no path between V1 and V2, print -1.

题目描述：

已知一个图，求其中从起点到终点的最短路径长度。

输入格式：

输入数据包含多组测试用例，每组数据第一行包含4个正整数 N,M,s,t，分别表示点数，边数，起点和终点。接下来 M 行，每行包含三个正整数 x,y,z，表示点 x 和点 y 之间存在一条边，边长为 z。

输出格式：

对于每组数据，输出一个整数，表示从起点到终点的最短路径长度。如果不存在从起点到终点的路径则输出 -1。

输入样例：

5 7 1 5
1 2 2
1 3 3
2 3 1
2 4 5
3 5 4
4 5 1
3 4 1
5 8 1 5
1 2 2
1 3 3
1 4 1
2 3 1
2 4 5
3 5 4
4 5 1
3 4 1

输出样例：

7
-1

算法思路：

本题是单源最短路径问题，可以使用 Dijkstra 算法求解。在 Dijkstra 算法中，需要使用一个优先队列来维护当前距离起点最近的点，每次取出队首的元素，并更新与其相邻的点的距离。同时需要使用一个 dis 数组来记录起点到每个点的最短距离，初始时所有距离都设置为无穷大，起点的距离为0。

算法流程如下：

1. 初始化 dis 数组，将起点的距离设置为0，其余点的距离设置为无穷大。

2. 将起点加入优先队列。

3. 当优先队列不为空时，取出队首元素，并更新与其相邻的点的距离。

4. 如果某个点的距离发生了更新，则将其加入优先队列中。

5. 重复步骤3-4，直到队列为空。

6. 如果终点的距离为无穷大，则表示不存在从起点到终点的路径，输出-1，否则输出终点的距离。

C++ 代码如下：

用c++解决这个问题：描述 After finishing the "Village Construction Project", the provincial government built more roads to make the trips between two villages more convenient. Then there is a new problem, which path is the shortest path between village V1 and V2? 输入 The first line of each test case contains four integers N, M, V1, V2 (1<=N, M, V1, V2<=1000; V1 != V2). Still, N and M represent the number of villages and the number of roads respectively. Then N lines follow, and every line contains three integers Ai, Bi, and Vi (1<=Ai, Bi <=N, Ai != Bi, 1<=Vi<=1000 ), meaning there is a road between village Ai and village Bi with its cost Vi. The inputs terminate at the end of the file (EOF). 输出 For each test case, output the cost of the shortest path between V1 and V2. If there is no path between V1 and V2, print -1.

这是一个经典的最短路径问题，可以使用 Dijkstra 算法来解决。以下是C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;

struct edge {
    int to, cost;
};

typedef pair<int, int> P;

int n, m, v1, v2;
vector<edge> G[1005];
int d[1005];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P>> que;
    memset(d, INF, sizeof(d));
    d[s] = 0;
    que.push(make_pair(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i = 0; i < G[v].size(); i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

int main() {
    while (scanf("%d %d %d %d", &n, &m, &v1, &v2) == 4) {
        for (int i = 1; i <= n; i++) G[i].clear();
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            G[a].push_back((edge){b, c});
            G[b].push_back((edge){a, c});
        }
        dijkstra(v1);
        if (d[v2] == INF) printf("-1\n");
        else printf("%d\n", d[v2]);
    }
    return 0;
}

算法的核心是 dijkstra 函数，该函数使用了优先队列来实现单源最短路径的计算。当然，这里也可以使用其他的最短路径算法，比如 Bellman-Ford 或者 Floyd 等。