AtCoder abc394 E-Palindromic Shortest Path

题目：Palindromic Shortest Path
题目链接：https://atcoder.jp/contests/abc394/tasks/abc394_e
题意：给你一个有向图的邻接矩阵\(C\)，\(C_{ij}=\)'-'代表从点\(i\)到点\(j\)没有边，否则\(C_{ij}\)代表点\(i\)到点\(j\)的边上的字母，试问对于每一个点对\((i,j)\)间的所有连通路径，是否存在由连通路径上的字母组成的字符串是回文串（含空串）的情况，若存在，找到回文串的最短长度\(len\)并使\(A_{ij}=len\)，否则\(A_{ij}=-1\)，输出矩阵\(A\)。
思路：先找到可以直接确定的\(A_{ij}\)：\(i=j\)时，存在空串，\(A_{ij}=0\)；\(C_{ij}\neq\)'-'时，\(i\)和\(j\)间存在一条直接连通的路径，即存在长度为1的回文串，\(A_{ij}=1\)。其它的\(A_{ij}\)可以由上述已知的答案推算：若\(A_{xy}\neq-1\)，且\(i\)到\(x\)和\(y\)到\(j\)间都存在边，且边上的字母相同，即说明\(i\)到\(j\)存在一个回文串"\(C_{ix}+A_{xy}代表的回文串+C_{yj}\)"，其长度为\(A_{xy}+2\)，\(A_{ij}=min(A_{ij},A_{xy}+2)\)。
实现：dfs
时间复杂度分析：矩阵范围为\(n^2\)（1≤n≤100），对于每个\(A_{xy}\)可以扩展\(n^2\)次，故时间复杂度为\(O(n^4)\)。
参考代码：
[code]#include#define int long longusing namespace std;#define endl '\n'#define mod 1000000007#define PII pair#define x first#define y secondconst int N=110;int ans[N][N];char c[N][N];int n; void solve(){        cin>>n;        queueq;        for(int i=1;ic[j];                        if(i==j) ans[j]=0,q.push({i,j});                        else if(c[j]!='-') ans[j]=1,q.push({i,j});                        else ans[j]=-1;                }        }        while(!q.empty()){                PII xtoy=q.front();                q.pop();                for(int i=1;i