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