洛谷P1462 通往奥格瑞玛的道路

二分答案+最短路SPFA

二分交费最多的一次的钱数

然后只将符合要求的边加入图中

如果到终点的最短路大于等于血量 或者直接起点不能到达终点

那么说明不符合要求 需要加大答案

时间复杂度 (log答案）* Ek

需要注意如果本来就不能到达

那么直接输出AFK

 

1 #include 
     
        2 #define LL long long  3 #define For(i,j,k) for(int i=j;i<=k;i++)  4 using namespace std ;  5  6 const int N = 10011 , M = 50011 ;  7 struct node{ 8     LL to,pre,val ;  9 }e[M*2];10 struct edge{11     LL x,y,val ; 12 }beg[M];13 LL n,m,b,cnt,point[N],head[N],mx,blood,dist[N] ;14 bool visit[N] ;  15 queue
      
        Q ; 16 17 inline LL read() 18 {19     LL x = 0 , f = 1 ; 20     char ch = getchar() ; 21     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 22     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 23     return x * f ; 24 }25 26 inline void add(int x,int y,int val) 27 {28     e[cnt].to = y ; 29     e[cnt].pre = head[x] ; 30     e[cnt].val = val ; 31     head[x] = cnt++ ; 32 }33 34 inline bool check( int mid ) 35 {36     LL u,v ; 37     For(i,0,n) head[i] = -1,dist[i] = (1LL<<62) ; 38     cnt = 0 ; 39     For(i,1,m) {40         if( point[beg[ i ].x] > mid ) continue ; 41         if( point[beg[ i ].y] > mid ) continue ; 42         add( beg[ i ].x,beg[ i ].y,beg[ i ].val ) ; 43         add( beg[ i ].y,beg[ i ].x,beg[ i ].val ) ; 44     }45     while(!Q.empty()) Q.pop() ; 46     Q.push(1) ; dist[ 1 ] = 0 ; visit[ 1 ] = 1 ;  47     while(!Q.empty()) {48         u = Q.front() ;49         Q.pop() ;  50         visit[u] = 0 ; 51         for(int i=head[u];~i;i=e[i].pre) {52             v = e[ i ].to ; 53             if( dist[ u ] +  e[ i ].val < dist[ v ] ) {54                 dist[ v ] = dist[ u ] + e[ i ].val ;   55                 if( !visit[ v ] ) {56                     visit[ v ] = 1 ; 57                     Q.push(v) ; 58                 }59             }60         }61     }62     if( dist[n]>=blood || dist[n]==dist[0] ) return 0 ;   // 血量不够 或者 不能到达  63     return 1 ;  64 }65 66 inline void erfen() 67 {68     LL l = 0 , r = mx+1,mid ; 69     while( l < r ) {70         mid = ( l+r )/2 ; 71         if( check( mid ) ) 72             r = mid ; 73         else 74             l = mid+1 ;  75     } 76     if(r==mx+1) {77         printf("AFK\n") ;78         exit(0) ;  79     }80     printf("%d\n",r) ; 81 }82 83 int main() 84 {85     n = read() ; m = read() ; blood = read() ; 86     For(i,1,n) point[ i ] = read(),mx = max(mx,point[ i ]) ;  87     For(i,1,m) {88         beg[ i ].x = read() ; beg[ i ].y = read() ; beg[ i ].val = read() ; 89     }90     erfen() ; 91     return 0 ; 92 }