用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 等。