【HDU】3873 Invade the Mars 最短路

HDU】3873 Invade the Mars 最短路"/>

【HDU】3873 Invade the Mars 最短路

传送门：【HDU】3873 Invade the Mars

题目分析：还真是有点意思的一道题，要求到达某个点就必须要取消所有对这个点的保护（即保护这个点的点全部被走过），那么我们只需要对Dijkstra算法略作修改即可：如果一个点在被访问的时候还是被保护的，那么它的最短路我们仍旧给他计算，但是不给他入队列，然后每次取出一个点的时候，由于Dijkstra的标号永久化的特性，取出来的点一定是已经计算好最短路了的，取消这个点u对其他点的保护，并用它更新那些被他保护的点v的最短路（d[v] = max ( d[v] , d[u] )，因为到达v点的时间要么是取消u点对其的保护之前或正好到，要么就是取消后才可能到），如果取消这个点x对某个点y的保护后点y不再被保护，则将点y入队。通过这种思想，我们可以轻松AC。（当然我AC的不轻松。。。）

PS：数据弱了，貌似没有爆int。。。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REV( i , n ) for ( int i = n - 1 ; i >= 0 ; -- i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define REPF( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define REPV( i , a , b ) for ( int i = a - 1 ; i >= b ; -- i )#define CLR( a , x ) memset ( a , x , sizeof a )typedef long long LL ;const int MAXN = 3005 ;
const int MAXE = 70005 ;
const int MAXH = 70005 ;
const LL INF = 1e15 ;struct Edge {int v , c , n ;Edge ( int var = 0 , int cost = 0 , int next = 0 ) :v ( var ) , c ( cost ) , n ( next ) {}
} ;struct Heap {int idx ;LL w ;Heap ( LL _w = 0 , int _idx = 0 ) :w ( _w ) , idx ( _idx ) {}
} ;struct priority_queue {Heap heap[MAXH] ;int top ;void init () {top = 1 ;}int cmp ( const Heap &a , const Heap &b ) {return a.w < b.w ;}void push ( LL w , int idx ) {heap[top] = Heap ( w , idx ) ;int o = top ++ ;while ( o > 1 && cmp ( heap[o] , heap[o >> 1] ) )swap ( heap[o] , heap[o >> 1] ) , o >>= 1 ;}int front () {return heap[1].idx ;}int empty () {return top == 1 ;}void pop () {heap[1] = heap[-- top] ;int o = 1 , p = o , l = o << 1 , r = o << 1 | 1 ;while ( o < top ) {if ( l < top && cmp ( heap[l] , heap[p] ) )p = l ;if ( r < top && cmp ( heap[r] , heap[p] ) )p = r ;if ( p == o )break ;swap ( heap[o] , heap[p] ) ;o = p , l = o << 1 , r = o << 1 | 1 ;}}
} ;struct Dij {priority_queue q ;Edge E[MAXE] ;int H[MAXN] , cntE ;LL d[MAXN] ;bool done[MAXN] ;int n , m ;int s , t ;int num[MAXN] ;LL mmax[MAXN] ;Edge P[MAXE] ;int A[MAXN] , cntP ;void init () {cntE = 0 ;CLR ( H , -1 ) ;cntP = 0 ;CLR ( mmax , 0 ) ;CLR ( A , -1 ) ;}void addedge ( int u , int v , int c ) {E[cntE] = Edge ( v , c , H[u] ) ;H[u] = cntE ++ ;}void add ( int u , int v ) {P[cntP] = Edge ( v , 0 , A[u] ) ;A[u] = cntP ++ ;}void dijkstra () {q.init () ;FOR ( i , 1 , n )d[i] = INF ;CLR ( done , 0 ) ;d[s] = 0 ;q.push ( d[s] , s ) ;while ( !q.empty () ) {int u = q.front () ;q.pop () ;if ( done[u] )continue ;done[u] = 1 ;for ( int i = A[u] ; ~i ; i = P[i].n ) {int v = P[i].v ;d[v] = max ( d[v] , d[u] ) ;if ( 0 == ( -- num[v] ) )q.push ( d[v] , v ) ;}for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v , c = E[i].c ;if ( d[v] > d[u] + c ) {d[v] = d[u] + c ;if ( !num[v] )q.push ( d[v] , v ) ;}}}}void input () {int u , v , c ;scanf ( "%d%d" , &n , &m ) ;s = 1 , t = n ;REP ( i , m ) {scanf ( "%d%d%d" , &u , &v , &c ) ;addedge ( u , v , c ) ;}FOR ( i , 1 , n ) {scanf ( "%d" , &num[i] ) ;REP ( j , num[i] ) {scanf ( "%d" , &v ) ;add ( v , i ) ;}}}		void solve () {init () ;input () ;dijkstra () ;printf ( "%I64d\n" , d[t] ) ;}
} z ;int main () {int T ;scanf ( "%d" , &T ) ;while ( T -- )z.solve () ;return 0 ;
}