用C++写一个代码满足下列任务本关任务：给定一个加权负边有向图找到从给定源到给定目的地的成本最低的路径路径可能重复经过同一个点且该路径恰好有m条边编程要求首先输入图的节点数量n和边的数量e然后依次输入这e条边的信息每条边包含3项内容：顶点1的编号顶点2的编号权值。最后输入source和destination的编号以及路径的边数限制m输出source到destination的成本最低的路径长度并且该

#include #include #include #include using namespace std;

const int INF = 0x7fffffff; const int MAXN = 1005; const int MAXM = 20005;

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

int head[MAXN], cnt = 1;

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

int dis[MAXN], vis[MAXN], pre[MAXN], pre_id[MAXN];

void dijkstra(int s, int m) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[s] = 0; pq.push(make_pair(dis[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; i = edges[i].next) { int v = edges[i].to; int w = edges[i].w; if (dis[v] > dis[u] + w && pre_id[u] + 1 <= m) { dis[v] = dis[u] + w; pre[v] = u; pre_id[v] = pre_id[u] + 1; pq.push(make_pair(dis[v], v)); } } } }

int main() { int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; addEdge(u, v, w); } int s, t, k; cin >> s >> t >> k; pre_id[s] = 0; dijkstra(s, k); if (dis[t] == INF) cout << 2147483647 << endl; else cout << dis[t] << endl; return 0; }