哪个网站可以卖自己的设计,构建新发展格局,360游戏,网站开发的流程图A* 做法 \(f(p)g(p)h(p)\) #xff0c; \(f(p)\) 作为优先队列比较函数用来比较的值#xff0c; \(g(p)\) 是当前路径到 \(p\) 的距离#xff0c; \(h(p)\) 是 \(p\) 点到终点最短路#xff08;预处理可以得到#xff09;。 每个点出队次数 \(k\)#xff0c;就说明当前找… A* 做法 \(f(p)g(p)h(p)\) \(f(p)\) 作为优先队列比较函数用来比较的值 \(g(p)\) 是当前路径到 \(p\) 的距离 \(h(p)\) 是 \(p\) 点到终点最短路预处理可以得到。 每个点出队次数 \(k\)就说明当前找到的是到这个点的 \(k\) 短路。 关键代码 void astar(int bg)
{int cnt 0;A.push(ast(bg, 0));while (!A.empty()) {ast p A.top();A.pop();if (p.v N) {if (p.w E)break;E - p.w, Ans;}for (int i G[p.v].size() - 1; i 0; --i) {edge e G[p.v][i];A.push(ast(e.v, p.w e.w));}}return;
} 一道裸题 【SDOI2010】魔法猪学院 #include cstdio
#include vector
#include algorithm
#include queueusing namespace std;typedef double db;const int _N 5100;
const db INF 1e9;struct edge {int v;db w;edge(int v 0, db w 0): v(v), w(w) { }
};struct data {int v;db w;data(int v 0, db w 0): v(v), w(w) { }bool operator (const data tmp)const{return w tmp.w;}
};db E, dis[_N];struct ast {int v;db w;ast(int v 0, db w 0): v(v), w(w) { }bool operator (const ast tmp)const{return w dis[v] tmp.w dis[tmp.v];}
};priority_queuedata Q;
priority_queueast A;
vectoredge G[_N], H[_N];
int Ans, N, M;void Gins(int a, int b, db c) { G[a].push_back(edge(b ,c)); return; }void Hins(int a, int b, db c) { H[a].push_back(edge(b, c)); return; }void dfs(int x, db cost)
{if (cost dis[x] E) return;if (x N) {A.push(cost);return;}for (int i G[x].size() - 1; i 0; --i) {edge e G[x][i];dfs(e.v, cost e.w);}return;
}void init(int bg)
{for (int i 1; i N; i)dis[i] INF;Q.push(data(bg, dis[bg] 0));while (!Q.empty()) {data p Q.top();Q.pop();if (dis[p.v] ! p.w) continue;for (int i H[p.v].size() - 1; i 0; --i) {edge e H[p.v][i];if (dis[e.v] p.w e.w)dis[e.v] p.w e.w, Q.push(data(e.v, dis[e.v]));}}return;
}void astar(int bg)
{int cnt 0;A.push(ast(bg, 0));while (!A.empty()) {ast p A.top();A.pop();if (p.v N) {if (p.w E)break;E - p.w, Ans;}for (int i G[p.v].size() - 1; i 0; --i) {edge e G[p.v][i];A.push(ast(e.v, p.w e.w));}}return;
}int main()
{scanf(%d%d%lf, N, M, E);for (int i 1; i M; i) {int a, b;db c;scanf(%d%d%lf, a, b, c);Gins(a, b, c), Hins(b, a, c);}init(N);astar(1);printf(%d\n, Ans);return 0;
} 转载于:https://www.cnblogs.com/ghcred/p/9775373.html
