Solve the problem with c++ code, and give your code: Ack Country has N cities connected by M one-way channels. The cities occupied by the rebels are numbered 1, while the capital of Ack country is numbered N. In order to reduce the loss of effective force, you are permitted to use self-propelled bombers for this task. Any bomber enters the capital, your job is done. This seems simple enough, but the only difficulty is that many cities in Ack Country are covered by shields. If a city is protected by a shield, all shield generators that maintain the shield need to be destroyed before the bomber can enter or pass through the city. Fortunately, we know the cities where all the shield generators are located, and which cities' shields are being charged. If the bomber enters a city, all of its shield generators can be destroyed instantly. You can release any number of Bombermen and execute any command at the same time, but it takes time for bombermen to pass through the roads between cities. Please figure out how soon you can blow up Ack Nation's capital. The clock is ticking. 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. e.g., 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 <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int MAXN = 1005;
const int INF = 1e9;
int n, m, dist[MAXN][20], vis[MAXN][20], shield[MAXN][20];
vector<pair<int,int>> e[MAXN];

void Dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
    pq.push({0,{1,0}});
    dist[1][0] = 0;
    while (!pq.empty()) {
        int u = pq.top().second.first;
        int s = pq.top().second.second;
        pq.pop();
        if (vis[u][s]) continue;
        vis[u][s] = 1;
        for (auto v : e[u]) {
            int w = v.second;
            int t = v.first;
            if (shield[u][s] && shield[u][s] == shield[v.first][s]) continue;
            if (dist[t][s] > dist[u][s] + w) {
                dist[t][s] = dist[u][s] + w;
                pq.push({dist[t][s], {t, s}});
            }
        }
        for (int i = 1; i <= n; i++) {
            if (i != u && shield[i][s] && !vis[i][s]) {
                if (dist[i][s] > dist[u][s] + shield[i][s]) {
                    dist[i][s] = dist[u][s] + shield[i][s];
                    pq.push({dist[i][s], {i, s}});
                }
            }
        }
        if (s < 19 && !vis[u][s+1]) {
            if (dist[u][s+1] > dist[u][s] + 1) {
                dist[u][s+1] = dist[u][s] + 1;
                pq.push({dist[u][s+1], {u, s+1}});
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < 20; i++) {
        ans = min(ans, dist[n][i]);
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[u].push_back({v, w});
    }
    for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        while (k--) {
            int x;
            scanf("%d", &x);
            shield[x][i/20] |= (1<<(i%20));
        }
    }
    Dijkstra();
    return 0;
}

算法思路：

考虑到每个城市上可能有多个盾牌，因此我们用一个 20 位的二进制数来表示每个城市上的盾牌状态。例如，第 $i$ 个城市上有第 $j$ 和第 $k$ 个盾牌，则 $shield[i][j/20]$ 和 $shield[i][k/20]$ 中的第 $j\%20$ 和第 $k\%20$ 位均为 1。

在 Dijkstra 算法中，我们需要维护一个状态 $s$，表示当前已经摧毁了哪些盾牌。例如，如果 $s=11011_2$，则表示已经摧毁了第 0、1、3、4、5 个盾牌。我们可以用一个长度为 20 的二进制数来表示这个状态。

在更新距离时，我们需要分别考虑以下三种情况：

1. 如果当前城市有盾牌，且这个盾牌没有被摧毁，则不能通过这个城市。因此，我们在更新时需要判断这个盾牌是否已经被摧毁。

2. 如果当前城市上有盾牌，且当前状态 $s$ 中没有摧毁这个盾牌，则需要先摧毁这个盾牌，再继续前进。因此，我们在更新时需要判断这个盾牌是否已经被摧毁，并且在距离上加上摧毁盾牌所需要的时间。

3. 如果当前状态 $s$ 中还有未摧毁的盾牌，则需要先摧毁这些盾牌，再继续前进。因此，我们可以将状态 $s$ 中的一个 1 移到下一位，表示摧毁了下一个盾牌，并在距离上加上 1。

最终的答案为所有状态中到达目的地的最小距离。