Give a solution to the problem of the shortest path with a shield c++ code, the shortest output time.Input: Two positive integers N,M in the first row. The next M lines, each with three positive integers, indicate that there is a road leading from the city to the city. It takes w time for the bomber to cross this road. Then N lines, each describing a city's shield. The first is a positive integer n, representing the number of shield generators that maintain shields in the city. Then n_i city numbers between 1 and N, indicating the location of each shield generator. In other words, if your bomber needs to enter the city, the bomber needs to enter all the entered cities in advance. If n_i=0, the city has no shields. Guarantee n_i=0.Output: a positive integer, the minimum time to blow up the capital.Must be able to pass the following examples:Input: 6 6 1 2 1 1 4 3 2 3 3 2 5 2 4 6 2 5 3 2 0 0 0 1 3 0 2 3 5, Output: 6.

以下是使用Dijkstra算法解决带有防护罩的最短路问题的C++代码：

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 25;
const int MAXM = 45;

struct Edge {
    int to, next, w;
} edge[MAXM];

int main() {
    int head[MAXN], cnt=0;
    int dis[MAXN][MAXN], vis[MAXN];
    int shield[MAXN][MAXN], d[MAXN][MAXN];
    int n, m;

    memset(dis, INF, sizeof(dis));
    memset(head, -1, sizeof(head));
    memset(shield, 0, sizeof(shield));

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[cnt].to = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt++;
        dis[u][v] = min(dis[u][v], w);
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;
            shield[x][i] = 1;
        }
    }

    for (int s = 1; s <= n; s++) {
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i++) {
            d[s][i] = INF;
            if (shield[s][i]) {
                for (int j = 1; j <= n; j++) {
                    if (shield[s][j] && j != i) {
                        d[s][i] = min(d[s][i], dis[i][j]);
                    }
                }
            } else {
                d[s][i] = dis[s][i];
            }
        }
        pq.push({d[s][s], s});
        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (int i = head[u]; i != -1; i = edge[i].next) {
                int v = edge[i].to;
                if (d[s][v] > d[s][u] + edge[i].w) {
                    d[s][v] = d[s][u] + edge[i].w;
                    pq.push({d[s][v], v});
                }
            }
        }
    }

    int ans = INF;
    for (int i = 1; i <= n; i++) {
        if (shield[i][n]) continue;
        ans = min(ans, d[i][n]);
    }
    cout << ans << endl;

    return 0;
}

输入样例：

6 6
1 2 1
1 4 3
2 3 3
2 5 2
4 6 2
5 3 2
0
0
0
1 3
0
2 3 5

输出样例：

6