检查是否正确#includecstdio#includeiostreamusing namespace std;int map500500book500dis500cnt500u500v500c500;int mnsdwans=9999999;void dfsint veint lenint cnt ifcnt==w ifve==d ans=minlenans; return; forin
代码本身的语法是没有问题的,但是存在以下几个问题:
-
图的边权值可能为负数,但是实现的是基于DFS的暴力搜索,不能处理这种情况,会导致错误的结果。
-
对于没有路径的情况,输出应该是 "unreachable",而不是 "2147483647"。
-
对于无法到达目标点的情况,应该在搜索结束后判断 ans 是否被更新过,如果没有更新过,说明无法到达目标点。
-
程序中没有使用book数组来标记哪些点已经被访问过,可能会导致死循环或者重复遍历。
-
变量名不够语义化,比如 cnt 可以改为 step 表示已经走的步数。
-
使用了一些不必要的变量和数组,比如 cnt 数组和 dis 数组,可以直接使用 step 变量。
综上所述,建议对代码进行以下修改:
- 使用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;
}
- 添加 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;
}
}
}
- 修改输出无法到达的情况:
if(ans == INF) printf("unreachable");
else printf("%d", ans);
- 修改变量名:
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;
}
}
}
- 去掉不必要的数组和变量:
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;
}
}
}
原文地址: https://www.cveoy.top/t/topic/bvUy 著作权归作者所有。请勿转载和采集!