题面
大意：给一张(n)个点，(m)条边的有向图，保证能从(1)号点到(n)号点，边有正实数边权(e_i)，路径权值为边权和。问从(1)号点到(n)号点最多能选多少条本质不同的路径，使得这些路径权值和不超过给定的(E)？
(2leq nleq 5000,1leq mleq 200000,1leq e_i,Eleq 10^7)
题解
- 这是一道k短路裸题。因为你肯定要选前k短的。而且求k短路是一条条求出来的。
- 接下来的问题就是怎么求k短路。
- 可以理解为A*。估价函数就是这个点到终点的距离。但是这个做法非常没用。因为你不好分析他。
- 可以换一种思路，用最短路树。
- 最牛逼的做法可以看这里，这是标题上的可持久化可并堆。
- 我们发现这种做法，实际上就是变成了在最短路树上走，（记上次走的边是(e_1)，上上次是(e_2)），那每次可以：
- 往当前最末端的那个点的祖先走若干步，然后跳非树边。记这样子走可以走的边集为(S_{e_1})，就从(S_{e_1})中选择最小的那一条走。
- (e_1)这一步撤回来，往(S_{e_2})中(e_1)权值在后面的那条边走。
- 这种做法，每次从堆顶弹出都会确定一条当前还剩下的最短路，并最多产生两种本质不同的路径。总时间复杂度是(O(anslogn))的。
- 但是，我太弱了，可持久化可并堆很有可能写错，这怎么办呢？
- 我发现，完全可以让这个更新的过程弱一点，不往祖先走了，直接就看他自己的最小的那一条。
- 这样子，你想一想，发现，这东西太难卡了。那就这么写吧。
- 然后，你就赢了。
- 实测，瞎写写就能取得与可持久化可并堆差不多的成绩。
接下来是一些没什么用的话。
- 你可以用平衡树来做这道题。因为它能加入最小的，弹出最大的。这样你就能保证数据结构里维护着的始终不超过(k)条路经。
- 如果想更好一点，那就使平衡树里维护着的路径，（已经走的长度 估价长度）之和小于等于当前还能用的长度。
- 这个东西，如果用set来写，你就会拿到和普通的k短路一样的分数，太赚了
代码
#include<bits/stdc .h>
#define LL long long
#define eps 0.0000000001
#define MAXN 5000
#define MAXM 200000
using namespace std;
template<typename T>void Read(T &cn)
{
char c;int sig = 1;
while(!isdigit(c = getchar()))if(c == '-')sig = -1; cn = c-48;
while(isdigit(c = getchar()))cn = cn*10 c-48; cn*=sig;
}
template<typename T>void Write(T cn)
{
if(cn < 0) {putchar('-'); cn = 0-cn; }
int wei = 0; T cm = 0; int cx = cn; cn/=10;
while(cn)cm = cm*10 cn,cn/=10,wei ;
while(wei--)putchar(cm 48),cm/=10;
putchar(cx 48);
}
const double INF = 1e18;
const int MAXNUM = 8000000;
struct qwe{
double w;
int a,b,ne;
void getit() {scanf("%d %d %lf",&a,&b,&w); }
inline friend bool operator <(qwe a, qwe b) {return a.w < b.w; }
void mk(int cn, int cm, int cx, double cw) {a = cn; b = cm; ne = cx; w = cw; }
};
struct qwer{
int a; double b;
void mk(int cn, double cm) {a = cn; b = cm; }
inline friend bool operator <(qwer a, qwer b) {return a.b > b.b; }
};
int n,m;
double E, E0;
qwe a[MAXM 1], b[MAXM 1];
int alen;
int head[MAXN 1];
qwer dui[MAXNUM 1];
int dlen;
double lu[MAXN 1];
int ans;
int ci[MAXN 1];
void lian(int cn, int cm, double cx) {a[ alen].mk(cn,cm,head[cn],cx); head[cn] = alen; }
void pre_dij(int cn)
{
for(int i = 1;i<=n;i ) lu[i] = INF;
lu[cn] = 0; dlen = 0; dui[ dlen].mk(cn,0);
while(dlen)
{
while(dlen && (dui[1].b - lu[dui[1].a]) > eps) pop_heap(dui 1,dui (dlen--) 1);
if(!dlen) break;
int dang = dui[1].a; pop_heap(dui 1,dui (dlen--) 1);
for(int i = head[dang];i;i = a[i].ne)
{
int y = a[i].b;
if(lu[y] <= lu[dang] a[i].w) continue;
lu[y] = lu[dang] a[i].w;
dui[ dlen].mk(y,lu[y]); push_heap(dui 1,dui dlen 1);
}
}
}
int main()
{
scanf("%d %d %lf", &n, &m, &E);
for(int i = 1;i<=m;i ) b[i].getit();
alen = 0; memset(head,0,sizeof(head));
for(int i = 1;i<=m;i ) lian(b[i].b,b[i].a,b[i].w);
pre_dij(n); E0 = lu[1];
for(int i = 1;i<=m;i ) b[i].w = b[i].w - lu[b[i].a] lu[b[i].b];
alen = 0; memset(head,0,sizeof(head));
sort(b 1,b m 1); for(int i = m;i>=1;i--) lian(b[i].a, b[i].b, b[i].w);
ans = 0; dlen = 0;
dui[ dlen].mk(head[1],a[head[1]].w);
while(dlen)
{
int dang1 = dui[1].a; double dang2 = dui[1].b;
if(dang2 E0 > E) break; pop_heap(dui 1,dui (dlen--) 1);
if(a[dang1].b == n) {E -= dang2 E0; ans ; }
else {int cn = head[a[dang1].b]; dui[ dlen].mk(cn,dang2 a[cn].w); push_heap(dui 1,dui dlen 1); }
dang2 -= a[dang1].w; dang1 = a[dang1].ne; if(dang1) dui[ dlen].mk(dang1, dang2 a[dang1].w), push_heap(dui 1,dui dlen 1);
}
Write(ans); puts("");
return 0;
}