← 返回题目

题库练习遥远的牧场

← 上一题下一题 →

A2195 | $遥远的牧场$

来源USACO / 2012

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给出一个n*n的括号矩阵，从一个点走到相邻的同字符点需付出A的代价，到不同字符点需付出B的代价。求所有点对之间最短路的最大值。

输入格式

* 第 1 行：三个整数：N （1 <= N <= 30）、A （0 <= A <= 1,000,000） 和 B （0 <= B <= 1,000,000）。 * 第 1..N+1 行：每行包含一串长度为 N 的括号，这些 N 行共同形成一个 N x N 网格括弧。

输出格式

* 第 1 行：一个整数，指定 Bessie 可以在一对牧场之间旅行的最大时间（假设她总是遵循花费最少时间的路线）。

输入输出样例

输入 #1

3 1 2 
((( 
()( 
(()

输出 #1

C++ 编辑器

输入

输出