E - Palindromic Shortest Path
思路：
bfs，队列里存边即可。根据回文的特性，从长度为1和2的两种边开始找，往两边扩张。
要注意入队顺序，先入长度为1的边，完了再入长度为2的边，否则不能保证先找到的是最短的了。
代码：
//赛时写的史山
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
#define FU(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FD(i, a, b) for(int i = (a); i >= (b); -- i)
const int MOD = 1e9+7;
const int INF = 1e9;
char c[105][105];
int ans[105][105];
bool vis[105][105];signed main() {// cin.tie(0)->ios::sync_with_stdio(0);int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>c[i][j];ans[i][j]= (i==j?0:INF);}}queue<pair<pii,int>> qu;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(c[i][j]=='-')continue;qu.push({{i,j},1}); // 奇数型}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(c[i][j]=='-')continue;for(int k=1;k<=n;k++){if(c[i][j]==c[j][k] && i!=k){qu.push({{i,k},2}); //偶数型}}}}while(!qu.empty()){int i=qu.front().first.first,j=qu.front().first.second,k=qu.front().second;qu.pop();// cout<<i<<" "<<j<<" "<<k<<endl;ans[i][j]=min(ans[i][j],k);if(vis[i][j])continue;vis[i][j]=1;for(int l1=1;l1<=n;l1++){if(c[l1][i]=='-')continue;for(int l2=1;l2<=n;l2++){if(c[l1][i]== c[j][l2]){qu.push({{l1,l2},k+2});}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(ans[i][j]!=INF)cout<<ans[i][j]<<" ";else cout<<"-1 ";}cout<<endl;}return 0;
}
标答代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;int inf = 1000000010;int main() {int n;cin >> n;vector<vector<char>> c(n, vector<char>(n));rep(i, n) rep(j, n) cin >> c[i][j];vector<vector<int>> a(n, vector<int>(n, inf));queue<pair<int, int>> que;rep(i, n) {que.push({i, i});a[i][i] = 0;}rep(i, n) rep(j, n) {if (i == j or c[i][j] == '-') continue;que.push({i, j});a[i][j] = 1;}while (!que.empty()) {auto q = que.front(); que.pop();int i = q.first, j = q.second;rep(k, n) rep(l, n) {if (c[k][i] != '-' && c[j][l] != '-' && c[k][i] == c[j][l] && a[k][l] == inf) {a[k][l] = a[i][j] + 2;que.push({k, l});}}}rep(i, n) {rep(j, n) {cout << (a[i][j] == inf ? -1 : a[i][j]) << " \n"[j == n - 1];}}
}