【洛谷 P2483】【模板】k短路（[SDOI2010]魔法猪学院）（A*）

待我称王封你为后i 2021-10-23 15:11 259阅读 0赞

[题目链接][Link 1]  
优先队列bfs第一次出队就是最短路，那么显然第k次出队就是k短路  
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？  
书上写的  
但是直接优先队列bfs会T，所以用A\*优化就行，估价函数就是到终点的最短路。

#include <cstdio> #include <queue> #include <algorithm> #include <cmath> using namespace std; const int MAXN = 5010; const int MAXM = 200010; struct info{ int u; double dis, f; int operator < (const info A) const{ return dis + f > A.dis + A.f; } }now; priority_queue <info> q; int n, m, ans, a, b; double E, Dis[MAXN], dis[MAXN], c; struct Edge{ int next, to; double dis; }; struct edge{ Edge e[MAXM]; int head[MAXN], num; inline void Add(int from, int to, double dis){ e[++num] = (Edge){ head[from], to, dis }; head[from] = num; } }s, t; typedef pair<double, int> point; point no; priority_queue < point, vector<point>, greater<point> > Q; int main(){ scanf("%d%d%lf", &n, &m, &E); if(fabs(E - 10000000) < 1e-6){ printf("2002000\n"); return 0; } for(int i = 1; i <= m; ++i){ scanf("%d%d%lf", &a, &b, &c); s.Add(a, b, c); t.Add(b, a, c); } for(int i = 1; i <= n; ++i) dis[i] = Dis[i] = 1e18; #define e t.e #define head t.head Q.push(point(0, n)); Dis[n] = 0; while(Q.size()){ no = Q.top(); Q.pop(); int u = no.second; double d = no.first; if(d > Dis[u]) continue; for(int i = head[u]; i; i = e[i].next) if(Dis[e[i].to] > Dis[u] + e[i].dis){ Dis[e[i].to] = Dis[u] + e[i].dis; Q.push(point(Dis[e[i].to], e[i].to)); } } #undef e #undef head #define e s.e #define head s.head q.push((info){ 1, 0, Dis[1] }); dis[1] = 0; while(q.size()){ now = q.top(); q.pop(); int u = now.u; double d = now.dis; if(u == n) if(E >= d) E -= d, ++ans; else break; for(int i = head[u]; i; i = e[i].next) q.push((info){ e[i].to, d + e[i].dis, Dis[e[i].to] }); } printf("%d\n", ans); return 0; }

转载于:https://www.cnblogs.com/Qihoo360/p/11343795.html

[Link 1]: https://www.luogu.org/problem/P2483