写一个C++代码 给定一个 n 个点 m 条边的不含重边和自环的无向图。 点的编号为 1∼n ，边的编号为 1∼m 。 在 t=0 时刻，你位于 1 号点。 你的任务是尽可能早的抵达 n 号点。 第 i 条边连接点 ai 和点 bi ，通过此边需要花费的时间为 ci 。 在整个移动过程中，你只有在整数时刻才能离开某一点前往另一点。 此外，第 i 个点有 ki 个禁止离开时刻。 在每个点的禁止离开时刻，你无法离开该点前往其它点。 请你计算抵达 n 号点的最早可能时刻。 输入格式 第一行包含两个整数 n,m 。 接下来 m 行，其中第 i 行包含三个整数 ai,bi,ci ，表示第 i 条边连接点 ai 和 bi ，通过此边需要花费的时间为 ci 。 接下来 n 行，其中第 i 行首先包含一个整数 ki ，表示第 i 个点有 ki 个禁止离开时刻，随后包含 ki 个互不相同的升序排序的整数 tij ，表示所有禁止离开时刻。 输出格式 一个整数，表示抵达 n 号点的最早可能时刻。 如果无法抵达 n 号点，则输出 -1。

抱歉，我可以回答这个问题。这是一个最短路问题，可以使用 Dijkstra 算法求解。在 Dijkstra 算法中，需要维护一个距离数组 dist，表示从起点到每个点的最短距离。初始时，dist[1]=0，其余点的距离为正无穷。然后，每次选择一个距离最小的未确定点 u，更新其相邻点的距离，即如果从 u 到 v 有一条边 e，则更新 dist[v]=min(dist[v], dist[u]+e.weight)。同时，需要考虑每个点的禁止离开时刻，可以使用一个二维数组 forbid[i][j] 表示第 i 个点的第 j 个禁止离开时刻，如果当前时间与 forbid[i][j] 相等，则不能离开该点。最后，如果 dist[n] 仍为正无穷，则无法抵达 n 号点，否则 dist[n] 即为最早可能时刻。

相关问题

写一个C++代码 给定一个 n 个点 m 条边的不含重边和自环的无向图。 点的编号为 1∼n ，边的编号为 1∼m 。 在 t=0 时刻，你位于 1 号点。 你的任务是尽可能早的抵达 n 号点。 第 i 条边连接点 ai 和点 bi ，通过此边需要花费的时间为 ci 。 在整个移动过程中，你只有在整数时刻才能离开某一点前往另一点。 此外，第 i 个点有 ki 个禁止离开时刻。 在每个点的禁止离开时刻，你无法离开该点前往其它点。 请你计算抵达 n 号点的最早可能时刻。

抱歉，我可以回答这个问题。以下是 C 代码实现：

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

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;

struct Edge {
int to, w;
};

vector<Edge> G[MAXN];
int n, m, k[MAXN];
int d[MAXN], vis[MAXN];

void dijkstra() {
memset(d, INF, sizeof(d));
memset(vis, 0, sizeof(vis));
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
d[1] = 0;
q.push(make_pair(0, 1));
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].to;
int w = G[u][i].w;
if (vis[v]) continue;
int t = d[u] + w;
if (t % 2 == 1 && k[v] == t) t++;
if (t < d[v]) {
d[v] = t;
q.push(make_pair(d[v], v));
}
}
}
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &k[i]);
}
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});
G[v].push_back((Edge){u, w});
}
dijkstra();
printf("%d\n", d[n]);
return 0;
}

该代码使用 Dijkstra 算法求解最短路，其中需要注意的是，如果当前时间为奇数且等于某个点的禁止离开时刻，需要将时间加一，以保证能够离开该点。

用C++写这道题的代码：给定一个 n 个点 m 条边的不含重边和自环的无向图。 点的编号为 1∼n ，边的编号为 1∼m 。 在 t=0 时刻，你位于 1 号点。 你的任务是尽可能早的抵达 n 号点。 第 i 条边连接点 ai 和点 bi ，通过此边需要花费的时间为 ci 。 在整个移动过程中，你只有在整数时刻才能离开某一点前往另一点。 此外，第 i 个点有 ki 个禁止离开时刻。 在每个点的禁止离开时刻，你无法离开该点前往其它点。 请你计算抵达 n 号点的最早可能时刻。

抱歉，我可以回答这个问题。以下是用C语言写这道题的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100005
#define MAXM 200005
#define INF 0x3f3f3f3f

typedef struct {
    int v, w, next;
} Edge;

Edge edge[MAXM];
int head[MAXN], cnt;
int n, m, k[MAXN];
int dis[MAXN], vis[MAXN];

void addEdge(int u, int v, int w) {
    edge[++cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void dijkstra() {
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == 0 || dis[j] < dis[u])) {
                u = j;
            }
        }
        vis[u] = 1;
        for (int j = head[u]; j; j = edge[j].next) {
            int v = edge[j].v, w = edge[j].w;
            if (!vis[v] && dis[u] % w == 0 && dis[u] / w + 1 < k[v]) {
                dis[v] = dis[u] + w;
            }
        }
    }
}

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);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &k[i]);
    }
    dijkstra();
    printf("%d\n", dis[n]);
    return 0;
}

这是一个基于 Dijkstra 算法的解法，时间复杂度为 O(n^2)。在每次选取最短路的时候，我们需要枚举所有未访问的点，找到距离起点最近的那个点。然后，我们遍历以该点为起点的所有边，更新与该点相邻的点的最短路。在更新的时候，我们需要判断当前时刻是否可以离开该点，以及是否可以在下一个整数时刻到达相邻的点。如果可以，我们就更新最短路。最终，我们得到的最短路就是抵达 n 号点的最早可能时刻。