# Orange Boy Can You Solve It Out? Ep. 31 (Hard)

If you prefer easier problem, please visit here

思考题 for dw

# Childish War (Hard)

Miss. Broken Tail(Wei Duan) is the Math teacher of NFLS Class 8 Junior 3.She is a kind teacher.

Miss. East(Fang Dong) is the Math teacher of NFLS Class 4 Junior 3.She is a kind teacher too.

Tail loves walking around the Xuanwu Lake to relax. So does East.

There are N islands numbered from 1 to N on Xuanwu Lake and there are M bidirectional weighted edges connecting them. It is made sure that the islands are connected and no edge has negative weight.

Tail is located at island S and East is located at island T. They decided to play a childish game.

The game has Q rounds, in each round East chooses an positive integer R and draw a circle centered at her position with the radius R1.

Tail will choose an radius R2 and draw a circle centered at her position with R2 as radius too. The *score* of Tail will be calculated as follows:

Let's call the number of islands included in Tail's circle but not in East's circle X.Let's call the number of islands included in Tail's circle and in East's circle Y. Then the score of Tail's circle is aX+bY where a and b are given.

For each query, find the max score of Tail's circle.

# Example

**Input**

graph={

[1,2,2],

[2,3,2],

[1,4,2],

[4,3,2],

[1,3,3],

}

S=1 T=3 a=3 b=1

Query={

[1],

[4]

}

**Output**

10

4

**Explain**

Q1:Tail can draw a circle of radius 3 so that X=3(1,2,4) Y=1(3).

Q2:Tail can draw a circle of radius 4 so that X=0 Y=4(1,2,3,4).

# Constriants

Subtask 1(50%):0<=a,b<=1e9,1<=N,M,Q<=1e5

Subtask 2(25%):0<=|a|,|b|<=1e9,1<=N,M,Q<=1000

Subtask 3(25%):0<=|a|,|b|<=1e9,1<=N,M,Q<=100000

版权声明：

作者：XGN

链接：__https://blog.hellholestudios.top/archives/331__

来源：Hell Hole Studios Blog

文章版权归作者所有，未经允许请勿转载。

## 共有 1 条评论