吃菜
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师是一个吃货，今天他胃口大开，晚上去了一家菜式丰盛的餐厅，餐厅一共有 n 种菜，徐老师想要吃 m 种菜，每种菜只吃一次，并且他为了获得纯粹的口感，决定吃完一种再开始吃下一种。
徐老师吃第 i 种菜会获得 ai 点满足值，这个餐厅还给徐老师提供了 k 条建议，第 i 条建议是说如果徐老师在吃完 xi 这种菜之后紧接着吃 yi 这种菜，会额外获得 ci 点满足值。
徐老师想要知道他选择哪些菜来吃，按怎样的顺序来吃可以让自己获得的满足值最大，他想你告诉他他可以获得的最大的满足值是多少。
输入格式
第一行包含三个整数 n, m, k(1 <= m <= n <= 18, 0 <= k <= n * (n - 1)) 。
第二行包含 n 个整数 ai(0 <= ai <= 10 ^ 9) 。
接下来 k 行，每行三个整数 xi, yi, ci(1 <= xi, yi <= n, 0 <= ci <= 10 ^ 9) 。
保证对于不同的建议 i, j ，不会出现 xi = xj 且 yi = yj 的情况。
输出格式
输出一行，包含一个整数，表示徐老师可以获得的最大满足值。
样例
2 2 1
1 1
2 1 1325CSP-S寒假提高班专题二
- 状态
- 已结束
- 规则
- IOI
- 题目
- 6
- 开始于
- 2025-1-22 18:15
- 结束于
- 2025-2-1 18:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 31
