网站建设中html网页,个人导航网站怎么备案,建网站不想用怎样撤销,贵阳网站建设包首页178. 第K短路 - AcWing题库
给定一张 N 个点#xff08;编号 1,2…N#xff09;#xff0c;M 条边的有向图#xff0c;求从起点 S 到终点 T 的第 K 短路的长度#xff0c;路径允许重复经过点或边。
注意#xff1a; 每条最短路中至少要包含一条边。
输入格式
第一行包… 178. 第K短路 - AcWing题库
给定一张 N 个点编号 1,2…NM 条边的有向图求从起点 S 到终点 T 的第 K 短路的长度路径允许重复经过点或边。
注意 每条最短路中至少要包含一条边。
输入格式
第一行包含两个整数 N 和 M。
接下来 M 行每行包含三个整数 A,B 和 L表示点 A 与点 B 之间存在有向边且边长为 L。
最后一行包含三个整数 S,T 和 K分别表示起点 S终点 T 和第 K 短路。
输出格式
输出占一行包含一个整数表示第 K 短路的长度如果第 K 短路不存在则输出 −1。
数据范围
1≤S,T≤N≤1000 0≤M≤104 1≤K≤1000 1≤L≤100
输入样例
2 2
1 2 5
2 1 4
1 2 2输出样例
14 A * 算法定义了一个对当前状态 x 的估价函数 f(x)g[x]h[x]其中 g[x] 为从初始状态到达当前状态的实际代价h[x] 为从当前状态到达目标状态的最佳路径的估计代价。每次取出 最优的状态f[x] 扩展其所有子状态可以用 优先队列 来维护这个值。 在求解 k 短路问题时令 h[x] 为从当前结点到达终点 T 的最短路径长度。可以通过在反向图上对结点 T 跑单源最短路预处理出对每个结点的这个值。 A*于一种经典的启发式搜索方法所谓启发式搜索就在于当前搜索结点往下选择下一步结点时可以通过一个启发函数来进行选择选择代价最少的结点作为下一步搜索结点而跳转其上。 传统的算法中深度优先搜索(DFS)和广度优先搜索(BFS)在展开子结点时均属于盲目型搜索也就是说它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中均需要试探完整个解集空间, 显然只能适用于问题规模不大的搜索问题中。而与DFS,BFS不同的是一个经过仔细设计的启发函数往往在很快的时间内就可得到一个搜索问题的最优解。 1、标记起点s为open计算起点的估计代价 2、选择open点集中估计代价最小的点 3、如果选中的点∈目标集合T即到达目标标记该点closed算法结束 4、否则还未到达目标标记该点closed对其周围直达的点计算估计代价如果周围直达的点未标记为closed将其标记为open如果已经标记为closed的如果重新计算出的估计代价比它原来的估计代价小更新估计代价并将其重新标记open。返回第2步。 ———————————————— 版权声明本文为CSDN博主「一叶执念」的原创文章遵循CC 4.0 BY-SA版权协议转载请附上原文出处链接及本声明。 原文链接https://blog.csdn.net/YiYeZhiNian/article/details/132056786 当起点和终点相同时K中隐含了一条长度为0的没有边的最短路但这条路是不对的因为起点和终点至少包含一条边所以K排除掉长度为0的最短路。此外K使得边不存在时astar不会返回0而是返回-1。
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
using namespace std;
typedef long long LL;#define f first
#define s second
const int N 1e3 2, M 2e4 3;
int n,m,S,T,K;
int h[N], hr[N], e[M], w[M], ne[M], idx;
int dist[N];
bool vis[N];
typedef pairint, int PII;
typedef pairint, PII PIII;void add(int H[], int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] H[a], H[a] idx;
}//估价函数
void Dijkstra() {memset(dist, 0x3f, sizeof dist);priority_queuePII, vectorPII, greaterPIIq;dist[T] 0;q.push({ dist[T],T });while (!q.empty()) {PII t q.top();//cout t.first t.second endl;q.pop();if (vis[t.s])continue;vis[t.s] 1;for (int i hr[t.s]; i ! -1; i ne[i]) {int s e[i], d w[i];if (dist[s] dist[t.s] d) {dist[s] dist[t.s] d;q.push({ dist[s], s });}}}
}int astar() {priority_queuePIII, vectorPIII, greaterPIIIq;int cnt[N] { 0 };q.push({ dist[S],{0,S} });while (!q.empty()) {auto t q.top();q.pop();cnt[t.second.second];//cout t.second.second cnt[t.second.second] endl;if (cnt[T] K)return t.second.first;int a t.second.second;for (int i h[a]; i ! -1; i ne[i]) {int j e[i];if (cnt[j] K) {q.push({ dist[j] t.second.firstw[i], {t.second.first w[i],j}});}}}return -1;
}int main() {scanf(%d%d, n, m);memset(h, -1, sizeof h);memset(hr, -1, sizeof hr);for (int i 1,a,b,c; i m; i) {scanf(%d%d%d, a, b, c);add(h, a, b, c);add(hr, b, a, c);}cin S T K;if (S T)K;Dijkstra();/*cout KKKKKKKKKKKKKKKKKKKKKKKK endl;for (int i 1; i n; i) {cout dist[i] endl;}*/printf(%d\n, astar());return 0;
}
