#PU1285. USACO 2023 January Contest, Platinum — Problem 2. Mana Collection

    ID: 1540 传统题 5000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan23来源:usaco.orgscoring:equal_test_cases动态规划

USACO 2023 January Contest, Platinum — Problem 2. Mana Collection

USACO 2023 January Contest, Platinum — Problem 2. Mana Collection

题目描述

Note: The time limit for this problem is 5s, 2.5 times the default. The memory limit for this problem is 512MB, twice the default. Bessie has recently taken an interest in magic and needs to collect mana for a very important spell. Bessie has NN (1≤N≤181\le N\le 18) mana pools, the iith of which accumulates mim_i mana per second (1≤mi≤1081\le m_i\le 10^8). The pools are linked by a collection of MM (0≤M≤N(N−1)0\le M\le N(N-1)) directed edges (ai,bi,ti)(a_i,b_i,t_i), meaning that she can travel from aia_i to bib_i in tit_i seconds (1≤ai,bi≤N1\le a_i, b_i\le N, ai≠bia_i\neq b_i, 1≤ti≤1091\le t_i\le 10^9). Whenever Bessie is present at a pool, she can collect all the mana stored at that location, emptying it. At time 00, all mana pools are empty, and Bessie can select any pool to start at. Answer QQ (1≤Q≤2⋅1051\le Q\le 2\cdot 10^5) queries, each specified by two integers ss and ee (1≤s≤1091\le s\le 10^9, 1≤e≤N1\le e\le N). For each query, determine the maximum amount of mana Bessie can collect in ss seconds if she must be at mana pool ee at the end of the ssth second.

输入格式

First line contains NN and MM. Next line contains m1,m2,…,mNm_1,m_2,\dots, m_N. Next MM lines contain ai,bi,tia_i,b_i,t_i. No ordered pair (ai,bi)(a_i,b_i) appears more than once in the input. Next line contains QQ. Next QQ lines contain two integers ss and ee.

输出格式

QQ lines, one for each query.

数据范围

Inputs 3-4: N≤10,Q≤100N\le 10, Q\le 100 Inputs 5-9: N≤10N\le 10 Inputs 10-14: Q≤100Q\le 100 Inputs 15-17: N=16N = 16 Inputs 18-20: N=17N = 17 Inputs 21-24: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2
5
50
100
1090
First query: Bessie takes 5 mana from pool 1 after 5 seconds.
Second query: Bessie takes 50 mana from pool 2 after 5 seconds.
Third query: Bessie takes 100 mana from pool 1 after 100 seconds.
Fourth query: Bessie takes 90 mana from pool 1 after 90 seconds and 1000 mana
from pool 2 after 100 seconds.

样例 2

4 8
50000000 100000000 20000000 70000000
1 2 20
2 1 50
2 3 90
1 3 40
3 1 10
4 1 25
1 4 5
4 3 70
3
8 3
1000000000 1
500000 4
160000000
239999988050000000
119992550000000
An example where Bessie is able to collect much larger amounts of mana.