请用C++完成该题
时间: 2024-02-28 11:56:02 浏览: 14
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 3005;
const int MAXM = 70005;
struct Edge {
int v, w;
Edge(int _v, int _w) : v(_v), w(_w) {}
};
vector<Edge> G[MAXN]; // 原图
vector<Edge> G2[MAXN]; // 新图
int n, m, s, t;
int n_i[MAXN], p_i[MAXN][MAXN];
int d[MAXN][1<<8]; // 状态压缩
void buildGraph() {
scanf("%d%d", &n, &m);
s = 1, t = n;
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(Edge(v, w));
}
for (int i = 1; i <= n; i++) {
scanf("%d", &n_i[i]);
for (int j = 0; j < n_i[i]; j++) {
scanf("%d", &p_i[i][j]);
}
}
// 建新图
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n_i[i]; j++) {
int u = p_i[i][j];
for (int k = 0; k < n_i[u]; k++) {
int v = p_i[u][k];
G2[i].push_back(Edge(v, INF));
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < G[i].size(); j++) {
int u = i, v = G[i][j].v, w = G[i][j].w;
for (int k = 0; k < n_i[v]; k++) {
int x = p_i[v][k];
G2[u].push_back(Edge(x, w));
}
}
}
}
void dijkstra() {
memset(d, INF, sizeof(d));
d[s][0] = 0;
priority_queue<pair<int, pair<int, int> > > q;
q.push(make_pair(0, make_pair(s, 0)));
while (!q.empty()) {
int u = q.top().second.first;
int dis = -q.top().first;
int state = q.top().second.second;
q.pop();
if (dis > d[u][state]) continue;
for (int i = 0; i < G2[u].size(); i++) {
int v = G2[u][i].v, w = G2[u][i].w;
int next_state = state;
for (int j = 0; j < n_i[v]; j++) {
int x = p_i[v][j];
next_state |= (1 << (x-1));
}
if (d[v][next_state] > dis+w) {
d[v][next_state] = dis+w;
q.push(make_pair(-d[v][next_state], make_pair(v, next_state)));
}
}
}
}
int main() {
buildGraph();
dijkstra();
printf("%d\n", d[t][(1<<n_i[t])-1]);
return 0;
}
```