题目
点这里看题目。
分析
好有意思的题目。
根据题目的要求，当 (r) 确定的时候有对路径的限制：
[rle xle frac{p}{p-1}r
]
我们可以得到一条路径对于 (r) 的限制：
[frac{p-1}{p}xle rle x
]
设 (P(u)) 为 1 到 (u) 的路径的长度的集合，设 (R(u)={r|exists xin P(u),frac{p-1}{p}xle rle x}) ，可以发现 (R(u)) 其实是多个区间的并集。
那么设 (R(u)=igcup_{i=1}^k[l_i,r_i]) ，可以发现 (kle log_{frac{p}{p-1}} max{r}) ！！！
这是因为，如果我们将有交的区间合并，并且将区间按左端点排序，那么一定有 (l_{i+1}ge r_ige frac{p}{p-1} l_i) 。因此左端点位置的增长速度近似于指数。
按一下计算器可以发现区间数量不会太多（最多也只有 800 左右），所以我们可以对每个点暴力维护一下它的区间。
考虑走过一条边。设 (q=frac{p-1}{p}) 对于区间 ([qx_1,x_1],[qx_2,x_2]) ，如果有 (qx_1le qx_2le x_1le x_2) ，则对于任意实数 (d>0) ，都会有 (q(x_1+d)le q(x_2+d)le (x_1+d)le (x_2+d)) 。所以走过一条边之后，原先有交的区间还是有交，我们不会需要拆开已合并的区间。
合并可以通过归并的方式做到线性，查询的时候可以二分。设 (S=log_{frac{p}{p-1}}A) ，则时间复杂度为 (O((n+m)C+qlog_2C)) 。
小结：
- 关于区间数量的分析简直太棒了，所以能简则简是必需的。
代码
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
typedef long long LL;
typedef pair<LL, LL> Seg;
const int MAXN = 5e5 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
struct Edge
{
int to, nxt; LL w;
}Graph[MAXN];
vector<Seg> seg[MAXN], add;
int q[MAXN];
int head[MAXN], in[MAXN];
int N, M, Q, P, cnt;
bool save[MAXN];
void AddEdge( const int from, const int to, const LL w )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
Graph[cnt].w = w, head[from] = cnt, in[to] ++;
}
void Clean()
{
cnt = 0;
rep( i, 1, N ) head[i] = in[i] = 0, seg[i].clear();
}
void Topo()
{
int h = 1, t = 0, u, v;
rep( i, 1, N ) if( ! in[i] ) q[++ t] = i;
while( h <= t )
{
u = q[h ++];
for( int i = head[u] ; i ; i = Graph[i].nxt )
if( ! ( -- in[v = Graph[i].to] ) ) q[++ t] = v;
}
}
void Merge( vector<Seg> &ret, const vector<Seg> &ins )
{
static vector<Seg> tmp; tmp.clear();
int s1 = ret.size(), s2 = ins.size(), i = 0, j = 0;
while( i < s1 && j < s2 )
{
if( ret[i] < ins[j] ) tmp.push_back( ret[i ++] );
else tmp.push_back( ins[j ++] );
}
while( i < s1 ) tmp.push_back( ret[i ++] );
while( j < s2 ) tmp.push_back( ins[j ++] );
s1 = tmp.size(), ret.clear();
rep( i, 0, s1 - 1 ) save[i] = true;
rep( i, 1, s1 - 1 )
if( tmp[i - 1].second >= tmp[i].first )
tmp[i] = Seg( tmp[i - 1].first, MAX( tmp[i].second, tmp[i - 1].second ) ), save[i - 1] = false;
rep( i, 0, s1 - 1 ) if( save[i] ) ret.push_back( tmp[i] );
}
int main()
{
int T; read( T );
rep( cas, 1, T )
{
read( N ), read( M ), read( Q ), read( P ); Clean();
rep( i, 1, M ) { int a, b; LL c;
read( a ), read( b ), read( c );
AddEdge( a, b, c );
}
Topo();
seg[1].push_back( Seg( 0, 0 ) );
rep( i, 1, N )
{
int u = q[i], s = seg[u].size();
for( int j = head[u] ; j ; j = Graph[j].nxt )
{
add.clear();
rep( k, 0, s - 1 )
add.push_back( Seg( seg[u][k].first + ( P - 1 ) * Graph[j].w,
seg[u][k].second + P * Graph[j].w ) );
Merge( seg[Graph[j].to], add );
}
}
while( Q -- ) { int f; LL r;
read( f ), read( r );
vector<Seg> :: iterator res = upper_bound( seg[f].begin(), seg[f].end(), Seg( P * r, P * r ) );
if( res != seg[f].end() && res->first == P * r ) putchar( '1' );
else if( res == seg[f].begin() ) putchar( '0' );
else putchar( ( -- res )->second >= P * r ? '1' : '0' );
}
puts( "" );
}
return 0;
}