文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/P3057
D
e
s
c
r
i
p
t
i
o
n
Description
Description
给定一张
n
×
n
n\times n
n×n的括号矩阵，规定走到相邻相同括号的代价为
a
a
a，走到相邻不相同括号的代价为
b
b
b 求所有最短路的最大值
数据范围：
n
≤
30
n\leq 30
n≤30
S
o
l
u
t
i
o
n
Solution
Solution
枚举点跑最短路即可
一定要松弛！一定要松弛！一定要松弛！
C
o
d
e
Code
Code
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std
;int n
,a
,b
,dis
[31][31],ans
;
bool vis
[31][31];
char s
[31][31];
struct node
{int x
,y
;};
queue
<node
>q
;
const int dx
[4]={-1,0,1,0};
const int dy
[4]={0,1,0,-1};
inline void bfs(int stx
,int sty
)
{
memset(vis
,0,sizeof(vis
));
memset(dis
,0x3f,sizeof(dis
));
while(q
.size()) q
.pop();
q
.push((node
){stx
,sty
});
vis
[stx
][sty
]=true;dis
[stx
][sty
]=0;
while(q
.size())
{
node u
=q
.front();q
.pop();
for(register int i
=0;i
<4;i
++)
{
node v
=u
;
v
.x
+=dx
[i
];v
.y
+=dy
[i
];
if(v
.x
<1||v
.x
>n
||v
.y
<1||v
.y
>n
) continue;
if(dis
[v
.x
][v
.y
]>dis
[u
.x
][u
.y
]+((s
[u
.x
][u
.y
]==s
[v
.x
][v
.y
])?a
:b
))
{
dis
[v
.x
][v
.y
]=dis
[u
.x
][u
.y
]+((s
[u
.x
][u
.y
]==s
[v
.x
][v
.y
])?a
:b
);
if(!vis
[v
.x
][v
.y
]) q
.push(v
),vis
[v
.x
][v
.y
]=true;
}
}vis
[u
.x
][u
.y
]=false;
}
for(register int i
=1;i
<=n
;i
++) for(register int j
=1;j
<=n
;j
++) ans
=max(ans
,dis
[i
][j
]);
return;
}
signed main()
{
scanf("%d%d%d\n",&n
,&a
,&b
);
for(register int i
=1;i
<=n
;i
++) scanf("%s",s
[i
]+1);
for(register int i
=1;i
<=n
;i
++) for(register int j
=1;j
<=n
;j
++) bfs(i
,j
);
printf("%d",ans
);
}
