[QBXT 8.12 NOIP 提高模拟] T4 最短路计数
出题人太菜,暂无测试数据。
题目描述
给定一张包含 \(n\) 个点的有向无环图,点的编号从 \(1\) 到 \(n\)。
- 对于所有 \(1 \leq i \leq n-1\),存在一条从 \(i\) 到 \(i+1\) 的长度为 \(a_i\) 的有向边。
- 对于所有 \(1 \leq i \leq n-2\),存在一条从 \(i\) 到 \(i+2\) 的长度为 \(b_i\) 的有向边。
- 对于所有 \(1 \leq i \leq n-3\),存在一条从 \(i\) 到 \(i+3\) 的长度为 \(c_i\) 的有向边。
现在,定义 \(d(s, t)\) 表示从点 \(s\) 到点 \(t\) 的最短路径。你的任务是求出所有可能的 \(d(s, t)\) 之和。
输入输出格式
输入格式
第一行一个正整数 \(T\),表示测试数据组数。
每组测试数据第一行一个正整数 \(n\)。
第二行 \(n-1\) 个整数 \(a_i\).
第三行 \(n-2\) 个整数 \(b_i\).
第四行 \(n-3\) 个整数 \(c_i\).
输出格式
对于每组测试数据,输出一行一个整数,表示答案。
样例
输入
2
4
1 1 1
1 1
1
5
1 2 3 4
2 3 4
3 4
输出
6
31
数据范围
本题共有\(5\)个测试点,每个\(20\)分。
测试点编号 | \( n\) | \(\sum n\) | 特殊性质 |
---|---|---|---|
\(1\) | \(\le 1000\) | \(\le 10000\) | 无 |
\(2\) | \(\le 20000\) | \(\le 10^5\) | \(b_i=a_i+a_{i+1},c_i=a_i+a_{i+1}+a_{i+2}\) |
\(3\) | \(\le 50000\) | \(\le 10^5\) | \(c_i=a_i+a_{i+1}+a_{i+2}\) |
\(4\) | \(\le 70000\) | \(\le 1.5\times 10^5\) | 无 |
\(5\) | \(\le 10^5\) | \(\le 3\times 10^5\) | 无 |
对于所有测试数据,\(1\le n\le 10^5,1\le a_i,b_i,c_i\le 10^4,\sum n\le 3\times 10^5,1\le T\le 10^4\)
信息
- ID
- 1067
- 难度
- (无)
- 分类
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者