Submission #63046436

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
using namespace std;
 
int main(){
    int N;
    cin >> N;
    vector<string> C(N);
    for (int i = 0; i < N; i++){
        cin >> C[i];
    }
    const int INF = numeric_limits<int>::max() / 2;
    // dp[i][j] : 最短のパリンドローム経路の長さ（頂点 i から j）
    vector<vector<int>> dp(N, vector<int>(N, INF));
    queue<pair<int,int>> que;
 
    // 初期状態：空文字列（各頂点で始まるもの）
    for (int i = 0; i < N; i++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
using namespace std;
 
int main(){
    int N;
    cin >> N;
    vector<string> C(N);
    for (int i = 0; i < N; i++){
        cin >> C[i];
    }
    const int INF = numeric_limits<int>::max() / 2;
    // dp[i][j] : 最短のパリンドローム経路の長さ（頂点 i から j）
    vector<vector<int>> dp(N, vector<int>(N, INF));
    queue<pair<int,int>> que;
 
    // 初期状態：空文字列（各頂点で始まるもの）
    for (int i = 0; i < N; i++){
        dp[i][i] = 0;
        que.push({i, i});
    }
    // 1辺のパリンドローム：単一文字はパリンドローム
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(C[i][j] != '-' && dp[i][j] > 1){
                dp[i][j] = 1;
                que.push({i,j});
            }
        }
    }
 
    // 事前に各頂点への逆向き辺（pred）と各頂点から出る辺（succ）を文字ごとにまとめる
    vector<vector<vector<int>>> pred(N, vector<vector<int>>(26));
    vector<vector<vector<int>>> succ(N, vector<vector<int>>(26));
    for (int u = 0; u < N; u++){
        for (int v = 0; v < N; v++){
            char ch = C[u][v];
            if(ch == '-') continue;
            int letter = ch - 'a';
            succ[u][letter].push_back(v);
            pred[v][letter].push_back(u);
        }
    }
 
    while(!que.empty()){
        auto [i, j] = que.front();
        que.pop();
        int d = dp[i][j];
        // 両側に同じ文字を追加する
        for(int letter = 0; letter < 26; letter++){
            // i に対する逆向き辺 u->i
            const auto &vec1 = pred[i][letter];
            // j に対する順向き辺 j->v
            const auto &vec2 = succ[j][letter];
            for (int u : vec1){
                for (int v : vec2){
                    int nd = d + 2;
                    if(dp[u][v] > nd){
                        dp[u][v] = nd;
                        que.push({u,v});
                    }
                }
            }
        }
    }
 
    // 出力：各 (i,j) に対して答え
    // dp[i][j] が INF の場合はパリンドローム経路は存在しないので -1 とする
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            if(dp[i][j] == INF) cout << -1 << " ";
            else cout << dp[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

Submission Info

Judge Result