传送门

题目描述：

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

Sample Input

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

Sample Output

5

思路：

先处理所有括号与其他括号的边，然后枚举所有点跑一遍spfa，最短路径最大值就是答案；
处理边的时候，因为是无向边，所以只需要拓展两个方向就可以出现所有的情况了

这里要用堆优化spfa 不然TLE

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,c1,c2;
char s[10000];
int a[1000][1000];
int dx[3]={0,0,1};
int dy[3]={0,1,0};
int ans,tot;
int next[20000],head[20000],to[20000],val[20000];
int dis[20000];
struct cmp
{
    bool operator()(const int &a,const int &b)
    {
        return dis[a]>dis[b];
    }
};
bool visit[2000];
void spfa(int x)
{
    priority_queue<int,vector<int>,cmp>q;
    memset(dis,0x3f,sizeof dis);
    memset(visit,false,sizeof visit);
    dis[x]=0;visit[x]=true;q.push(x);
    while(q.size())
    {
        int tmp=q.top();q.pop();
        visit[tmp]=false;
        for(int i=head[tmp];i;i=next[i])
        {
            if(dis[to[i]]>dis[tmp]+val[i])
            {
                dis[to[i]]=dis[tmp]+val[i];
                if(!visit[to[i]])
                q.push(to[i]),visit[to[i]]=true;
            }
        }
    }       
    for(int i=1;i<=n*n;i++)
        if(dis[i]<0x3f3f3f3f)
            ans=max(ans,dis[i]);
}
void add(int x,int y,int v)
{
    next[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    val[tot]=v;
}
void check(int x,int y)
{
    for(int i=1;i<=2;i++)
    {
        int dxx=dx[i]+x;
        int dyy=dy[i]+y;
        if(dxx<1||dyy>n||dxx>n||dyy<1)
            continue;
        if(a[x][y]==a[dxx][dyy])
        {
            add((x-1)*n+y,(dxx-1)*n+dyy,c1);
            add((dxx-1)*n+dyy,(x-1)*n+y,c1);
        }
        else 
        {
            add((x-1)*n+y,(dxx-1)*n+dyy,c2);
            add((dxx-1)*n+dyy,(x-1)*n+y,c2);
        }
        
    }
}
int main()
{
    scanf("%d%d%d",&n,&c1,&c2);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",&s[0]);
        for(int j=0;j<n;j++)
            a[i][j+1]=(s[j]=='('?1:2);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            check(i,j);
    for(int i=1;i<=n*n;i++)spfa(i);
    printf("%d",ans);
}