魔法猪学院

魔法猪学院

新建一个优先队列,将源点s加入到队列中;
从优先级队列中弹出f(p)最小的点p,如果点p就是t,则计算t出队的次数;
如果当前为t的第k次出队,则当前路径的长度就是s到t的第k短路的长度,算法结束;
否则遍历与p相连的所有的边,将扩展出的到p的邻接点信息加入到优先级队列

# include <iostream>
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>
# include <queue>
# define RG register
# define IL inline
# define ll long long
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;IL ll Read(){RG char c = getchar(); RG ll x = 0, z = 1;for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';return x * z;
}const int MAXN(5010), MAXM(400010);
const double EPS(1e-10);
int n, m, ft[MAXN], cnt, vis[MAXN], ans;
double dis[MAXN], E;
struct Edge{int to, nt;double w;
} edge[MAXM];
queue <int> Q;
struct Dist{double g; int id;IL bool operator <(RG Dist B) const{return dis[id] + g > dis[B.id] + B.g;}
} x;
priority_queue <Dist> Qk;IL void Add(RG int u, RG int v, RG double w){edge[cnt] = (Edge){v, ft[u], w}; ft[u] = cnt++;
}IL void Bfs(){dis[n] = 0; vis[n] = 1; Q.push(n);while(!Q.empty()){RG int u = Q.front(); Q.pop();for(RG int e = ft[u]; e != -1; e = edge[e].nt){if(!(e & 1)) continue;RG int v = edge[e].to; RG double w = edge[e].w;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;if(!vis[v]) vis[v] = 1, Q.push(v);}}vis[u] = 0;}
}IL void Kth(){Qk.push((Dist){0, 1});while(!Qk.empty()){x = Qk.top(); Qk.pop();if(x.g - E > EPS || EPS > E) break;if(x.id == n) ans++, E -= x.g;for(RG int e = ft[x.id]; e != -1; e = edge[e].nt){if(e & 1) continue;RG int v = edge[e].to; RG double w = edge[e].w;if(x.g + w - E > EPS) continue;Qk.push((Dist){x.g + w, v});}}printf("%dn", ans);
}int main(){Fill(ft, -1); Fill(dis, 127);n = Read(); m = Read(); scanf("%lf", &E);for(RG int i = 1; i <= m; i++){RG int u = Read(), v = Read(); RG double w;scanf("%lf", &w);Add(u, v, w); Add(v, u, w);}Bfs();Kth();return 0;
}