@[dustbin1415](/user/71956) 我帮你康康……（话说这算不算CTJ啊）
by 小杨小小杨 @ 2021-09-13 20:42:35
dijkstra看看教程吧，说实话真不好懂
by 离·清梦 @ 2021-09-13 20:44:01
@[离·清梦](/user/355093) Dij不是最短路中最简单的吗……
by 小杨小小杨 @ 2021-09-13 20:44:49
@[小杨小小杨](/user/315398) 你谷公约，对着题解手打不算
by dustbin1415 @ 2021-09-13 20:45:16
@[dustbin1415](/user/71956) ……
by 小杨小小杨 @ 2021-09-13 20:46:48
@[小杨小小杨](/user/315398) 不算 CTJ 吧？
by int64 @ 2021-09-13 20:48:23
啊这，K短噩梦至今A*不会qwq
by 无咕_ @ 2021-09-13 20:49:34
@[dustbin1415](/user/71956) 你主函数的que不用pop吗？
by 小杨小小杨 @ 2021-09-13 20:54:55
@[dustbin1415](/user/71956) 改好了
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge
{
int net, to;
double w;
};
struct Graph{
int tot, head[50005];
Edge edge[200005];
void add(int x, int y, double z)
{
edge[++tot] = (Edge){head[x], y, z};
head[x] = tot;
}
} G, R;
int n, m, ans = 0;
double E;
struct Node{
int No;
double dis;
friend bool operator<(Node x, Node y){
return x.dis > y.dis;
}
};
int vis[50005], fa[50005];
double dis[50005];
void dijkstra()
{
priority_queue<Node> que;
que.push((Node){n, 0});
memset(dis, 127, sizeof(dis));
dis[n] = 0;
while (!que.empty())
{
Node u = que.top();
que.pop();
if (vis[u.No])
continue;
vis[u.No] = 1;
for (int i = R.head[u.No]; i; i = R.edge[i].net)
{
Node v = (Node){R.edge[i].to, u.dis + R.edge[i].w};
if (dis[v.No] > v.dis)
dis[v.No] = v.dis, fa[v.No] = i, que.push(v);
}
}
}
int seq[50005], rt[50005];
bool cmp(int x, int y)
{
return dis[x] < dis[y];
}
struct heap
{
int left_son, right_son, dist, father;
double value;
} tree[21 * 50005];
int cnt = 0;
int heap_add(int f, double value)
{
int k = ++cnt;
tree[k].left_son = tree[k].right_son = tree[k].dist = 0,
tree[k].father = f,
tree[k].value = value;
return k;
}
int heap_merge(int x, int y)
{
if (!x || !y)
return x + y;
if (tree[x].value - tree[y].value > 0)
swap(x, y);
int k = ++cnt;
tree[k] = tree[x];
tree[k].right_son = heap_merge(tree[k].right_son, y);
if (tree[tree[k].left_son].dist < tree[tree[k].right_son].dist)
swap(tree[k].left_son, tree[k].right_son);
tree[k].dist = tree[tree[k].right_son].dist + 1;
return k;
}
struct ing
{
int x;
double ans;
friend bool operator<(ing x, ing y)
{
return x.ans > y.ans;
}
};
int main()
{
scanf("%d%d%lf", &n, &m, &E);
for (int i = 1; i <= m; i++)
{
int x, y;
double z;
scanf("%d%d%lf", &x, &y, &z);
if (x == n)
{
i--, m--;
continue;
}
G.add(x, y, z);
R.add(y, x, z);
}
dijkstra();
for (int i = 1; i <= n; i++)
seq[i] = i;
sort(seq + 1, seq + n + 1, cmp);
tree[0].dist = -1;
for (int i = 1; i <= n; i++)
{
int u = seq[i];
for (int j = G.head[u]; j; j = G.edge[j].net)
if (fa[u] != j)
rt[u] = heap_merge(rt[u], heap_add(G.edge[j].to, G.edge[j].w + dis[G.edge[j].to] - dis[u]));
rt[u] = heap_merge(rt[u], rt[G.edge[fa[u]].to]);
}
priority_queue<ing> que;
if (E - dis[1] < 0)
{
printf("0\n");
return 0;
}
E -= dis[1], ans++;
if (rt[1])
que.push((ing){rt[1], tree[rt[1]].value});
while (!que.empty())
{
ing u = que.top();que.pop();
if (E - (u.ans + dis[1]) < 0)
break;
E -= u.ans + dis[1], ans++;
if (tree[u.x].left_son)
que.push((ing){tree[u.x].left_son, u.ans - tree[u.x].value + tree[tree[u.x].left_son].value});
if (tree[u.x].right_son)
que.push((ing){tree[u.x].right_son, u.ans - tree[u.x].value + tree[tree[u.x].right_son].value});
if (rt[tree[u.x].father])
que.push((ing){rt[tree[u.x].father], u.ans + tree[rt[tree[u.x].father]].value});
}
printf("%d\n", ans);
return 0;
}
```
by 小杨小小杨 @ 2021-09-13 20:56:04
@[小杨小小杨](/user/315398) 啊这，没注意到orz，感谢orz
by dustbin1415 @ 2021-09-13 20:56:58