Description
iPig在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒……。 能量守恒……iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素……等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多 1 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 N 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾……现在的你呀！ 注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。
Input
第一行三个数 N、M、E 表示iPig知道的元素个数（元素从 1 到 N 编号）、iPig已经学会的魔法个数和iPig的总能量。 后跟 M 行每行三个数 si、ti、ei 表示 iPig 知道一种魔法，消耗 ei 的能量将元素 si 变换到元素 ti 。
Output
一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。
Sample Input
4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5
Sample Output
3
HINT
样例解释
有意义的转换方式共4种：
1->4，消耗能量 1.5
1->2->1->4，消耗能量 4.5
1->3->4，消耗能量 4.5
1->2->3->4，消耗能量 4.5
显然最多只能完成其中的3种转换方式（选第一种方式，后三种方式仍选两个），即最多可以转换3份样本。
如果将 E=14.9 改为 E=15，则可以完成以上全部方式，答案变为 4。
数据规模
占总分不小于 10% 的数据满足 N <= 6，M<=15。
占总分不小于 20% 的数据满足 N <= 100，M<=300，E<=100且E和所有的ei均为整数（可以直接作为整型数字读入）。
所有数据满足 2 <= N <= 5000，1 <= M <= 200000，1<=E<=107，1<=ei<=E，E和所有的ei为实数。
Source
Sdoi2010 Contest2 Day2
Solution
这题我们可以用第k短路来做（第k短路请点这里），我们发现从1~N，先完成消耗能量最少的转换方式，再走次少时，以此类推。。。直到总能量比第x短路消耗的能量少时，答案就是x-1了。
Tip：此题BZOJ上空间只有64MB，所以不能用STL的堆，要手写堆！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
#include<iostream> #include<cstdio> using namespace std; const int NN=5100,MM=200100; int n,m,tot,tot1,Next[MM],head[NN],tree[MM],Next1[MM],head1[NN],tree1[MM],x[2*NN],ans,HeapLen; double val[MM],val1[MM],dis[NN]; bool visit[NN]; double k; struct node { int u;double w; }heap[NN*500]; void add(int x,int y,double z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } void add1(int x,int y,double z) { tot1++; Next1[tot1]=head1[x]; head1[x]=tot1; tree1[tot1]=y; val1[tot1]=z; } void SPFA(int N) { int t=0,w=1; for (int i=1;i<=n;i++) visit[i]=false,dis[i]=99999999.0; x[1]=N;visit[N]=true;dis[N]=0.0; while (t!=w) { t++; if (t>2*n) t=1; int u=x[t]; visit[u]=false; for (int i=head1[u];i;i=Next1[i]) { int v=tree1[i]; if (dis[v]>dis[u]+val1[i]) { dis[v]=dis[u]+val1[i]; if (!visit[v]) { x[++w]=v; if (w>2*n) w=1; visit[v]=true; } } } } } void Swap(node &a,node &b) { node t=a;a=b;b=t; } bool calc(int x,int y) { if (heap[x].w+dis[heap[x].u]>heap[y].w+dis[heap[y].u]) return true; return false; } void push(node x) { heap[++HeapLen]=x; int j=HeapLen; while (j>1&&calc(j>>1,j)) Swap(heap[j],heap[j>>1]),j>>=1; } void pop() { Swap(heap[1],heap[HeapLen]); HeapLen--; int j=1; while (j<=HeapLen) { int l=j<<1,r=j<<1|1,t=j; if (l<=HeapLen&&calc(j,l)) t=l; if (r<=HeapLen&&calc(t,r)) t=r; if (t==j) break; Swap(heap[t],heap[j]); j=t; } } void A_Star() { node t; t.u=1;t.w=0.0; push(t); while (HeapLen>0) { node x=heap[1]; pop(); if (x.w>k) break; if (x.u==n&&x.w<=k) { k-=x.w; ans++; if (k==0) break; continue; } int u=x.u; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (x.w+val[i]+dis[v]<=k) { t.u=v;t.w=x.w+val[i]; push(t); } } } } int main() { scanf("%d%d%lf",&n,&m,&k); tot=tot1=0; for (int i=1;i<=m;i++) { int x,y;double z; scanf("%d%d%lf",&x,&y,&z); add(x,y,z);add1(y,x,z); } SPFA(n); ans=HeapLen=0; A_Star(); printf("%d\n",ans); return 0; } |
