很诡异地一道题,你看他问的是是否存在距离(din [dist,1.1dist])的路径.
你想一下这个(1.1)是个啥.好像不知道,先考虑暴力叭.
暴力你就(bfs),让点重复入队就好了,每个点维护一个(set),查询直接(lower\_bound)即可.
(Code:)
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define X first
#define Y second
#define rint read<int>
#define int long long
#define pb push_back
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 2e5 + 100 ;
struct edge { int to , next ; double data ; } e[N<<1] ;
set < double > p[N] ;
int n , m , Q , tot , head[N] ;
double dis[N] ;
bool vis[N] ;
inline void build (int u , int v , double w) {
e[++tot].next = head[u] ; e[tot].to = v ;
e[tot].data = w ; head[u] = tot ; return;
}
queue < int > q ;
inline void bfs (int cur) {
vis[cur] = true ; q.push ( cur ) ;
dis[cur] = 0 ; p[cur].insert ( dis[cur] ) ;
while ( ! q.empty () ) {
int j = q.front () ; q.pop () ; vis[j] = false ;
for (int i = head[j] ; i ; i = e[i].next) {
int k = e[i].to ;
for (auto it : p[j]) {
double dist = it + e[i].data ;
if ( p[k].find ( dist ) == p[k].end () ) {
if ( ! vis[k] ) { q.push ( k ) ; vis[k] = true ; }
p[k].insert ( dist ) ;
}
}
}
}
return ;
}
signed main (int argc , char * argv[]) {
n = rint () ; m = rint () ; Q = rint () ;
rep ( i , 1 , m ) {
int u = rint () , v = rint () , w = rint () ;
build ( u , v , w ) ;
}
bfs ( 1 ) ;
while ( Q -- ) {
int k = rint () ; double dist ;
scanf ("%lf" , & dist ) ;
auto pos = p[k].lower_bound ( dist ) ;
if ( pos == p[k].end () ) puts ("NO") ;
else if ( *pos <= dist * 1.1 ) puts ("YES") ;
else puts ("NO") ;
}
return 0 ;
}
然后我们发现,这个玩意儿的瓶颈在于转移的时候状态太多了.
然后我们考虑优化这个东西.
我们发现,如果说有三个距离(x,y,z)满足以下条件:
[cfrac{z}{1.1}<x<y<z
]
那么(y)就是没用的,显然答案的存在性不会因为缺少(y)而改变.
于是我们每次合并两个距离集合(即上述代码的转移,本质是两个距离集合的合并)就可以把这些(y)踢掉,使用类似于归并排序的思路即可解决.
这样你可能会认为还是会(TLE),但实际上它的复杂度是对的,为什么呢?
因为(1.1^{450})远远大于了所有权值的总和(10^{18}),也就是说一个点最多同时有(450)个状态被保留.
每次合并就是(Theta(450))的,查询随意,怎么搞都能过.
(Code:)
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
using std::lower_bound ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 2e5 + 100 ;
const int M = 477 ;
struct edge { int to , next ; double data ; } e[N] ;
queue < int > q ; double tmp[N] , dis[N][M] ;
int n , m , Q , tot , head[N] , cnt[N] , deg[N] ;
inline void build (int u , int v , double w) {
e[++tot].next = head[u] ; e[tot].to = v ;
e[tot].data = w ; head[u] = tot ; return;
}
inline void merge (int x , int y , double val) { // 从 x 到 y
int l = 1 , r = 1 , now = 0 ;
while ( l <= cnt[x] && r <= cnt[y] ) {
double cur = dis[x][l] + val ;
if ( cur < dis[y][r] ) {
while ( now >= 2 && (db)cur <= (db)tmp[now-1] * 1.1 && cur >= tmp[now] ) -- now ;
tmp[++now] = cur ; ++ l ;
} else {
while ( now >= 2 && (db)dis[y][r] <= (db)tmp[now-1] * 1.1 && dis[y][r] >= tmp[now] ) -- now ;
tmp[++now] = dis[y][r] ; ++ r ;
}
}
while ( l <= cnt[x] ) {
double cur = dis[x][l] + val ;
while ( now >= 2 && (db)cur <= (db)tmp[now-1] * 1.1 && cur >= tmp[now] ) -- now ;
tmp[++now] = cur ; ++ l ;
}
while ( r <= cnt[y] ) {
while ( now >= 2 && (db)dis[y][r] <= (db)tmp[now-1] * 1.1 && dis[y][r] >= tmp[now] ) -- now ;
tmp[++now] = dis[y][r] ; ++ r ;
}
rep ( i , 1 , now ) dis[y][i] = tmp[i] ;
cnt[y] = now ; return ;
}
inline void SPFA (int cur) {
rep ( i , 1 , n ) if ( ! deg[i] ) q.push ( i ) ;
++ cnt[cur] ; dis[cur][cnt[cur]] = 0.0 ;
while ( ! q.empty () ) {
int j = q.front () ; q.pop () ;
for (int i = head[j] ; i ; i = e[i].next) {
int k = e[i].to ; -- deg[k] ;
merge ( j , k , e[i].data ) ;
if ( ! deg[k] ) q.push ( k ) ;
}
}
return ;
}
signed main (int argc , char * argv[]) {
n = rint () ; m = rint () ; Q = rint () ;
rep ( i , 1 , m ) {
int u = rint () , v = rint () ; db w ; scanf ("%lf" , & w ) ;
build ( u , v , w ) ; ++ deg[v] ;
}
SPFA ( 1 ) ;
while ( Q -- ) {
int k = rint () , dist = rint () ;
int pos = lower_bound ( dis[k] + 1 , dis[k] + cnt[k] + 1 , dist ) - dis[k] ;
if ( (db)dis[k][pos] > (db)1.1 * dist || pos == cnt[k] + 1 ) puts ("NO") ; else puts ("YES") ;
}
return 0 ;
}