代码本身的语法是没有问题的,但是存在以下几个问题:

  1. 图的边权值可能为负数,但是实现的是基于DFS的暴力搜索,不能处理这种情况,会导致错误的结果。

  2. 对于没有路径的情况,输出应该是 "unreachable",而不是 "2147483647"。

  3. 对于无法到达目标点的情况,应该在搜索结束后判断 ans 是否被更新过,如果没有更新过,说明无法到达目标点。

  4. 程序中没有使用book数组来标记哪些点已经被访问过,可能会导致死循环或者重复遍历。

  5. 变量名不够语义化,比如 cnt 可以改为 step 表示已经走的步数。

  6. 使用了一些不必要的变量和数组,比如 cnt 数组和 dis 数组,可以直接使用 step 变量。

综上所述,建议对代码进行以下修改:

  1. 使用Dijkstra或Bellman-Ford算法来求解最短路径,这里以Dijkstra算法为例:
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x7fffffff;
const int MAXN = 505;

struct Edge {
    int to, w;
    Edge(int t, int ww): to(t), w(ww) {}
};

vector<Edge> adj[MAXN];
int dis[MAXN];
bool vis[MAXN];

void dijkstra(int s) {
    fill(dis, dis + MAXN, INF);
    dis[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    pq.push(make_pair(0, s));
    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].to, w = adj[u][i].w;
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push(make_pair(dis[v], v));
            }
        }
    }
}

int main() {
    int n, m, s, d, w;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        adj[u].push_back(Edge(v, c));
    }
    scanf("%d%d%d", &s, &d, &w);
    if(s == d) {
        printf("0");
        return 0;
    }
    dijkstra(s);
    if(dis[d] == INF) printf("unreachable");
    else printf("%d", dis[d]);
    return 0;
}
  1. 添加 vis 数组来标记哪些点已经被访问过:
bool vis[MAXN];

void dfs(int u, int step, int& ans) {
    if(u == d && step == w) {
        ans = 0;
        return;
    }
    if(step >= w || step >= ans) return;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].to, w = adj[u][i].w;
        if(!vis[v]) {
            vis[v] = true;
            dfs(v, step + 1, ans);
            vis[v] = false;
        }
    }
}
  1. 修改输出无法到达的情况:
if(ans == INF) printf("unreachable");
else printf("%d", ans);
  1. 修改变量名:
int step[MAXN];

void dfs(int u, int s, int& ans) {
    if(u == d && s == w) {
        ans = 0;
        return;
    }
    if(s >= w || s >= ans) return;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].to, wt = adj[u][i].w;
        if(!vis[v]) {
            vis[v] = true;
            dfs(v, s + 1, ans);
            vis[v] = false;
        }
    }
}
  1. 去掉不必要的数组和变量:
void dfs(int u, int s, int& ans) {
    if(u == d && s == w) {
        ans = 0;
        return;
    }
    if(s >= w || s >= ans) return;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].to, wt = adj[u][i].w;
        if(!vis[v]) {
            vis[v] = true;
            dfs(v, s + 1, ans);
            vis[v] = false;
        }
    }
}
检查是否正确#includecstdio#includeiostreamusing namespace std;int map500500book500dis500cnt500u500v500c500;int mnsdwans=9999999;void dfsint veint lenint cnt	ifcnt==w		ifve==d ans=minlenans;		return; 		forin

原文地址: https://www.cveoy.top/t/topic/bvUy 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录