样例解释
有意义的转换方式共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为实数。

Sdoi2010 Contest2 Day2

#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair<int, int> pii;typedef long long LL;const double PI = acos(-1.0);const int N = 5010;const int M = 200010;struct edge{    int to;    int pre;    double w;};struct Astar{    int cur;    double g;    double h;    bool operator<(const Astar &t)const    {        if (g + h == t.g + t.h)            return g <= t.g;        return g + h <= t.g + t.h;    }};struct Heap{    Astar A[1250010];    int sz;    void init()    {        sz = 0;    }    void up(const int &cur)    {        int fa = cur >> 1;        if (fa > 0 && A[cur] < A[fa])        {            swap(A[cur], A[fa]);            up(fa);        }    }    void down(const int &cur)    {        int lson = cur << 1;        int rson = lson | 1;        if (lson > sz)            return ;        int son;        if (rson > sz)            son = lson;        else            son = A[lson] < A[rson] ? lson : rson;        if (A[son] < A[cur])        {            swap(A[cur], A[son]);            down(son);        }    }    void push(const Astar &rhs)    {        A[++sz] = rhs;        up(sz);    }    void pop()    {        swap(A[1], A[sz]);        --sz;        down(1);    }    Astar top()    {        return A[1];    }    bool empty()    {        return !sz;    }};Heap heap;edge E[M], rE[M];int head[N], rhead[N], tot, rtot;double d[N];bitset<N>vis;void init(){    for (int i = 0; i < N; ++i)    {        d[i] = 1e20;        head[i] = rhead[i] = -1;    }    tot = 0;    rtot = 0;    vis.reset();    heap.init();}inline void add(int s, int t, double w){    E[tot].to = t;    E[tot].w = w;    E[tot].pre = head[s];    head[s] = tot++;    rE[rtot].to = s;    rE[rtot].w = w;    rE[rtot].pre = rhead[t];    rhead[t] = rtot++;}void rev_spfa(int s){    queue<int>q;    vis[s] = 1;    d[s] = 0.0;    q.push(s);    int i, now, v;    while (!q.empty())    {        now = q.front();        q.pop();        vis[now] = 0;        for (i = rhead[now]; ~i; i = rE[i].pre)        {            v = rE[i].to;            if (d[v] > d[now] + rE[i].w)            {                d[v] = d[now] + rE[i].w;                if (!vis[v])                {                    vis[v] = 1;                    q.push(v);                }            }        }    }}int main(void){    int n, m, i, a, b;    double e, w;    while (~scanf("%d%d%lf", &n, &m, &e))    {        init();        for (i = 0; i < m; ++i)        {            scanf("%d%d%lf", &a, &b, &w);            add(a, b, w);        }        rev_spfa(n);        Astar S;        S.cur = 1;        S.g = 0;        S.h = d[S.cur];        heap.push(S);        int r = 0;        Astar now, nxt;        while (!heap.empty())        {            now = heap.top();            heap.pop();            if (now.cur == n)            {                if (e >= now.g)                {                    e -= now.g;                    ++r;                }                else                    break;            }            for (i = head[now.cur]; ~i; i = E[i].pre)            {                nxt.cur = E[i].to;                nxt.g = now.g + E[i].w;                nxt.h = d[nxt.cur];                heap.push(nxt);            }        }        printf("%d\n", r);    }    return 0;}