BZOJ1975 [Sdoi2010]魔法猪学院 K短路 Astar A* 贪心

大家都很强， 可与之共勉 。

题意：
  给定一张图，一共有 k 的能量，求最多可以从 1→N 走多少次（路径不相同）？（每走一次都会消耗路径长的能量）。

题解：

  很明显是找出每一次都走还能走得最短路，这个贪心策略一定是正确的。所以我们用 A∗ 算法。
  手写堆的话一定要开够数组……
  BZOJ把空间改小了mmp，

/************************************************************** Problem: 1975 User: Lazer2001 Language: C++ Result: Accepted Time:1356 ms Memory:34572 kb ****************************************************************/

# include <bits/stdc++.h>

template < class T >  inline bool chkmin ( T& d, const T& x )  {  return ( d > x ) ? ( d = x ), 1 : 0 ;  }

# define N 5010
# define M 500010

template < class T >
class Heap  {
    private :
        T a [1500010] ; int len ;
    public :
        inline bool empty ( )  {
            return len == 0 ;
        }
        inline void clear ( )  {
            len = 0 ;
        }   
        inline void push ( const T& ele )  {
            a [++ len] = ele ;
            std :: push_heap ( a + 1, a + 1 + len, std :: greater < T > ( ) ) ;
        }
        inline T top ( )  {
            return a [1] ;
        }
        inline void pop ( )  {
            std :: pop_heap ( a + 1, a + 1 + len, std :: greater < T > ( ) ) ;
            -- len ;
        }
} ;

Heap < std :: pair < double, int > > Q ;

struct edge  {
    int to ;
    double w ;
    edge* nxt ;
} ;

struct Graph  {
    edge* head [N], g [M], *cur ;
    Graph ( )  {
        cur = g ;
        memset ( head, 0, sizeof head ) ;
    }
    inline void add_edge ( int u, int v, double w )  {
        *cur = ( edge )  { v, w, head [u] } ;  head [u] = cur ++ ;
    }
    inline edge*& operator [] ( const int& u )  {  return head [u] ;  }
} G, Rev ;

double dis [N] ;

inline void Dijkstra ( int S, int T )  {
    std :: fill ( dis, dis + 1 + S, 1e10 ) ;
    Q.clear ( ) ;
    Q.push ( std :: make_pair ( dis [S] = 0, S ) ) ; 
    while ( ! Q.empty ( ) )  {
        int u = Q.top ( ).second ; Q.pop ( ) ;
        for ( edge* it = Rev [u] ; it ; it = it -> nxt )  {
            if ( chkmin ( dis [it -> to], dis [u] + it -> w ) )  {
                Q.push ( std :: make_pair ( dis [it -> to], it -> to ) ) ;
            }
        }
    }
}

double sum ;

inline int Astar ( int S, int T )  {
    if ( dis [S] == 1e10 )  return 0 ;
    int cnt ( 0 ) ;
    Q.clear ( ) ;
    Q.push ( std :: make_pair ( dis [S], S ) ) ;
    while ( ! Q.empty ( ) )  {
        int u = Q.top ( ).second ; double d = Q.top ( ).first ;  Q.pop ( ) ;
        if ( u == T )  {
            if ( sum - d >= 0.0 )  {
                sum -= d ;
                ++ cnt ;
            }  else  return cnt ;
        }
        for ( edge* it = G [u] ; it ; it = it -> nxt )  {
            Q.push ( std :: make_pair ( d - dis [u] + dis [it -> to] + it -> w, it -> to ) ) ;
        }
    }
    return cnt ;
}

int main ( )  {
// freopen ( "in.txt", "r", stdin ) ;
    int n, m ;
    scanf ( "%d%d%lf", & n, & m, & sum ) ;
    while ( m -- )  {
        static int u, v ; static double w ;
        scanf ( "%d%d%lf", & u, & v, & w ) ;
        G.add_edge ( u, v, w ) ;
        Rev.add_edge ( v, u, w ) ;
    }
    Dijkstra ( n, 1 ) ;
    printf ( "%d\n", Astar ( 1, n ) ) ;
    return 0 ;
}