P2483.cpp

#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 5005, M = 2e5 + 5;
int n, m;
double E;

struct data { //A* 结构体
	double g;
	double h;
	int v;

	bool operator<(const data &a) const {
		return a.g + a.h < g + h;// 🌟⭐ 优化 主要在这里做的小的排前面
	}
};

struct edge {
	int to, next;
	double w;
} e1[M], e2[M];
int head1[N], head2[N], cnt = 0;

void addEdge(int u, int v, double w) {
	e1[++cnt].to = v;
	e1[cnt].w = w;
	e1[cnt].next = head1[u];
	head1[u] = cnt;
	e2[cnt].to = u;
	e2[cnt].w = w;
	e2[cnt].next = head2[v];
	head2[v] = cnt;// 反向建边
}

double dis[N];
int inq[N];
queue<int> p;

void spfa() {//很裸的最短路
	for (int i = 1; i <= n; i++)dis[i] = 99999999.9;
	p.push(n);
	dis[n] = 0;
	inq[n] = 1;
	while (p.size()) {
		int u = p.front();
		p.pop();
		for (int i = head2[u]; i; i = e2[i].next) {
			int v = e2[i].to;
			if (dis[v] > dis[u] + e2[i].w) {
				dis[v] = dis[u] + e2[i].w;
				if (!inq[v]) {
					inq[v] = 1;
					p.push(v);
				}
			}
		}
		inq[u] = 0;
	}
}

priority_queue<data> q;
int ans = 0;
int vis[N];//seen[] 表示到了某个点几次

void ASTAR(int maxN) {
	if (dis[1] == 99999999.9)return;// 不存在最短路径
	data cur, nt;
	cur.v = 1;
	cur.g = 0.0;
	cur.h = 0.0;
	q.push(cur);//入列
	while (q.size()) {
		cur = q.top();
		q.pop();
		if (cur.g > E)return;//（优化2）
		int u = cur.v;
		vis[u]++;
		if (vis[u] > maxN)continue;//（优化3）
		if (u == n) {
			E -= cur.g;
			ans++;
			continue;//到达目的地
		}
		for (int i = head1[u]; i; i = e1[i].next) {
			nt.v = e1[i].to;
			nt.h = dis[nt.v];
			nt.g = cur.g + e1[i].w;
			q.push(nt);
		}
	}
}

// A*算法是 BFS 的一种改进
// https://oi-wiki.org/search/astar/
// K短路题解： https://bit.ly/2CiVoSD
int main() {
	cin >> n >> m >> E;
	for (int i = 1; i <= m; i++) {
		int u, v;
		double w;
		cin >> u >> v >> w;
		addEdge(u, v, w);
	}
	spfa();
	if (E / dis[1] > 1000000) {// 特判卡点（似乎有点无耻）
		cout << 2002000 << endl;
		return 0;
	}
	ASTAR(E / dis[1]);//最多只有k/dis[1]种方案（优化1）
	cout << ans;
	return 0;
}