很杂乱的板子

// 大数加法
string largeadd(string &a, string &b)
{
    if (a.size() < b.size())
        swap(a, b);
    int p = 0;
    for (size_t i = 0; i < b.size(); i++)
    {
        int ai = a[a.size() - i - 1] - '0';
        int bi = b[b.size() - i - 1] - '0';
        int sum = ai + bi + p;
        if (sum >= 10)
        {
            p = 1;
            sum -= 10;
        }
        else
            p = 0;
        a[a.size() - 1 - i] = sum + '0';
    }
    for (size_t i = b.size(); i < a.size(); i++)
    {
        int ai = a[a.size() - i - 1] - '0';
        if (ai == '9' && p == 1)
        {
            a[a.size() - i - 1] = '0';
        }
        else
        {
            a[a.size() - i - 1] = ai + p + '0';
            p = 0;
        }
    }
    if (p == 1)
        a.insert(a.begin(), '1');
    return a;
}
// 大数减法
string largemin(string a, string b)
{
    int flag = 0;
    if (b.size() >= a.size() && b >= a)
    {
        swap(a, b);
        flag = 1;
    }
    int p = 0;
    for (size_t i = 0; i < b.size(); i++)
    {
        int ai = a[a.size() - 1 - i] - '0';
        int bi = b[b.size() - 1 - i] - '0';
        int diff = ai - bi - p;
        if (diff < 0)
        {
            p = 1;
            diff += 10;
        }
        else
            p = 0;
        a[a.size() - i - 1] = diff + '0';
    }
    for (size_t i = b.size(); i < a.size(); i++)
    {
        int ai = a[a.size() - i - 1] - '0';
        if (ai == 0 && p == 1)
        {
            a[a.size() - i - 1] = '9';
        }
        else
        {
            a[a.size() - i - 1] = ai - p + '0';
            p = 0;
        }
    }
    while (*a.begin() == '0' && a.size() > 1)
        a.erase(a.begin());
    if (flag)
        a.insert(a.begin(), '-');
    return a;
}
 
// DSU并查集
class DSU
{
private:
    vector<int> parent, rank, size;
    int count;
 
public:
    DSU(int n) : parent(n + 1), rank(n + 1, 0), size(n + 1, 1), count(n)
    {
        iota(all(parent), 0ll);
    }
 
    int find(int x)
    {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
 
    void merge(int i, int j)
    {
        int ri = find(i), rj = find(j);
        if (ri == rj)
        {
            return;
        }
 
        if (rank[ri] < rank[rj])
        {
            swap(ri, rj);
        }
        parent[rj] = ri;
        size[ri] += size[rj];
        if (rank[ri] == rank[rj])
        {
            rank[ri]++;
        }
        count--;
    }
 
    bool issame(int i, int j)
    {
        return find(i) == find(j);
    }
 
    int getsize(int x)
    {
        return size[find(x)];
    }
 
    int getgroups()
    {
        return count;
    }
};
// DSU end
 
// COMB 组合数 快速幂，乘法逆元 都在里面
const int N = 1e6;
vector<int> f(N), invf(N);
bool inited = 0;
int ksm(int base, int exp)
{
    int ans = 1;
    while (exp)
    {
        if (exp & 1)
        {
            ans = ans * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }
    return ans;
}
 
int inv(int x)
{
    return ksm(x, MOD - 2) % MOD;
}
 
void pre()
{
    if (inited)
    {
        return;
    }
    inited = 1;
    f[0] = 1;
    for (int i = 1; i < N; i++)
    {
        f[i] = f[i - 1] * i % MOD;
    }
 
    invf[N - 1] = inv(f[N - 1]);
    for (int i = N - 2; i >= 0; i--)
    {
        invf[i] = invf[i + 1] * (i + 1) % MOD;
    }
}
 
int comb(int n, int k)
{
    if (!inited)
    {
        pre();
    }
    if (k < 0 or k > n)
    {
        return 0;
    }
 
    return f[n] * invf[k] % MOD * invf[n - k] % MOD;
}
// comb end ----
 
// 马拉车
 
// 预处理
string preprocess(const string &s)
{
    string t = "^";
    for (char c : s)
    {
        t += "#" + string(1, c);
    }
    t += "#$";
    return t;
}
 
string longestPalindrome(const string &s)
{
    string T = preprocess(s);
    int n = T.size();
    vector<int> P(n, 0); // P[i] 记录以 t[i] 为中心的回文半径
    int C = 0, R = 0;    // C 是回文中心，R 是回文串的最右边界
    for (size_t i = 1; i < n - 1; i++)
    {
        // 确定对称位置
        int Mirror = 2 * C - i;
        if (i < R)
        {
            P[i] = min(P[Mirror], R - i);
        }
        // 尝试扩展边界
        while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
        {
            P[i]++;
        }
        // 如果当前回文串扩展超过了 R，更新中心和右边界
        if (i + P[i] > R)
        {
            C = i;
            R = i + P[i];
        }
    }
    // 找到最长的回文子串
    int maxLen = 0;
    int Centerindex = 0;
    for (size_t i = 0; i < n - 1; i++)
    {
        if (P[i] > maxLen)
        {
            maxLen = P[i];
            Centerindex = i;
        }
    }
    // 构造回文串
    int start = (Centerindex - maxLen) / 2;
    return s.substr(start, maxLen);
}
 
signed main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s;
    cin >> s;
    cout << longestPalindrome(s) << endl;
    return 0;
}
// end ---
 
// BIT 树状数组
 
class BIT
{
private:
    vector<int> c;
    int n;
 
    int lowbit(int x)
    {
        return x & -x;
    }
 
public:
    BIT(int size) : n(size)
    {
        c.resize(n + 1, 0);
    }
 
    BIT(vector<int> &arr) : n(arr.size())
    {
        c.resize(n + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            add(i, arr[i - 1]);
        }
    }
 
    void add(int i, int val)
    {
        while (i <= n)
        {
            c[i] += val;
            i += lowbit(i);
        }
    }
 
    int sum(int i)
    {
        int ans = 0;
        while (i)
        {
            ans += c[i];
            i -= lowbit(i);
        }
        return ans;
    }
 
    int query(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
 
    int get(int i)
    {
        return query(i, i);
    }
 
    int update(int i, int val)
    {
        auto delta = val = get(i);
        add(i, delta);
    }
 
    void clear()
    {
        fill(all(c), 0);
    }
 
    // 获取树状数组的大小
    int size()
    {
        return n;
    }
};
 
// BIT end
 
// 大数模下幂运算
 
// 快速幂函数，计算 base^exponent mod mod
long long modPow(long long base, long long exponent, long long mod)
{
    long long result = 1;
    base %= mod;
    while (exponent > 0)
    {
        if (exponent & 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exponent >>= 1;
    }
    return result;
}
 
void solve()
{
    long long x, p;
    string y;
    cin >> x >> y >> p;
    // 对 x 取模（防止数字过大）
    x %= p;
    // 特判：若 y 为 "0"，根据数学通常规定 x^0 = 1（注意：0^0一般认为1也可以根据题意而定）
    if (y == "0")
    {
        cout << 1 % p << "\n";
        return;
    }
    // 答案初始为 1
    long long ans = 1;
    // 对指数 y 的每一位进行处理
    for (char c : y)
    {
        int d = c - '0';
        // 将当前答案提升 10 次方后再乘上 x^d mod p
        ans = modPow(ans, 10, p);
        ans = (ans * modPow(x, d, p)) % p;
    }
    cout << ans % p << "\n";
}
 
// 大树模下 end ---
 
// 很多DP
 
// --------------------- 基础DP问题 ---------------------
 
// 01背包问题 - 每个物品最多选一次
int knapsack01(const vector<int> &weights, const vector<int> &values, int capacity)
{
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
 
    for (int i = 0; i < n; i++)
    {
        for (int j = capacity; j >= weights[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
 
    return dp[capacity];
}
 
// 完全背包问题 - 每个物品可以选无限次
int knapsackComplete(const vector<int> &weights, const vector<int> &values, int capacity)
{
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
 
    for (int i = 0; i < n; i++)
    {
        for (int j = weights[i]; j <= capacity; j++)
        {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
 
    return dp[capacity];
}
 
// 多重背包问题 - 每个物品有特定数量限制
int knapsackMultiple(const vector<int> &weights, const vector<int> &values,
                     const vector<int> &counts, int capacity)
{
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
 
    for (int i = 0; i < n; i++)
    {
        // 二进制优化 - 将k个物品拆成二进制表示
        int w = weights[i], v = values[i], c = counts[i];
        for (int k = 1; k <= c; k *= 2)
        {
            for (int j = capacity; j >= k * w; j--)
            {
                dp[j] = max(dp[j], dp[j - k * w] + k * v);
            }
            c -= k;
        }
 
        if (c > 0)
        {
            for (int j = capacity; j >= c * w; j--)
            {
                dp[j] = max(dp[j], dp[j - c * w] + c * v);
            }
        }
    }
 
    return dp[capacity];
}
 
// 最长递增子序列 (LIS)
int longestIncreasingSubsequence(const vector<int> &nums)
{
    int n = nums.size();
    if (n == 0)
        return 0;
 
    vector<int> dp(n, 1);
 
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (nums[i] > nums[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
 
    return *max_element(dp.begin(), dp.end());
}
 
// 最长递增子序列优化版 (O(nlogn))
int longestIncreasingSubsequenceOptimized(const vector<int> &nums)
{
    int n = nums.size();
    if (n == 0)
        return 0;
 
    vector<int> tails;
 
    for (int num : nums)
    {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end())
        {
            tails.push_back(num);
        }
        else
        {
            *it = num;
        }
    }
 
    return tails.size();
}
 
// 最长公共子序列 (LCS)
int longestCommonSubsequence(const string &text1, const string &text2)
{
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
 
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (text1[i - 1] == text2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
 
    return dp[m][n];
}
 
// 编辑距离
int editDistance(const string &word1, const string &word2)
{
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
 
    for (int i = 0; i <= m; i++)
        dp[i][0] = i;
    for (int j = 0; j <= n; j++)
        dp[0][j] = j;
 
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (word1[i - 1] == word2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
            }
        }
    }
 
    return dp[m][n];
}
 
// --------------------- 区间DP ---------------------
 
// 石子合并问题 - 求合并代价最小值
int mergeStones(const vector<int> &stones)
{
    int n = stones.size();
    if (n <= 1)
        return 0;
 
    // 前缀和加速区间求和
    vector<int> prefixSum(n + 1, 0);
    for (int i = 0; i < n; i++)
    {
        prefixSum[i + 1] = prefixSum[i] + stones[i];
    }
 
    // dp[i][j] 表示合并区间[i,j]的最小代价
    vector<vector<int>> dp(n, vector<int>(n, INF));
 
    // 初始化：单个石子无需合并
    for (int i = 0; i < n; i++)
    {
        dp[i][i] = 0;
    }
 
    // 按区间长度递推
    for (int len = 2; len <= n; len++)
    {
        for (int i = 0; i <= n - len; i++)
        {
            int j = i + len - 1;
 
            // 尝试在不同位置分割
            for (int k = i; k < j; k++)
            {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j + 1] - prefixSum[i]);
            }
        }
    }
 
    return dp[0][n - 1];
}
 
// --------------------- 树形DP ---------------------
 
// 树的最大独立集 (在树上选择不相邻的节点使得权值和最大)
void dfsIndependentSet(int node, int parent, const vector<vector<int>> &tree,
                       const vector<int> &values, vector<vector<int>> &dp)
{
    for (int child : tree[node])
    {
        if (child != parent)
        {
            dfsIndependentSet(child, node, tree, values, dp);
            // dp[node][0] - 不选当前节点
            dp[node][0] += max(dp[child][0], dp[child][1]);
            // dp[node][1] - 选当前节点
            dp[node][1] += dp[child][0];
        }
    }
    dp[node][1] += values[node]; // 加上当前节点的权值
}
 
int maxIndependentSet(const vector<vector<int>> &tree, const vector<int> &values)
{
    int n = values.size();
    // dp[i][0] - 不选节点i的最大值, dp[i][1] - 选节点i的最大值
    vector<vector<int>> dp(n, vector<int>(2, 0));
 
    dfsIndependentSet(0, -1, tree, values, dp);
    return max(dp[0][0], dp[0][1]);
}
 
// --------------------- 状态压缩DP ---------------------
 
// 旅行商问题 (TSP)
int tsp(const vector<vector<int>> &dist)
{
    int n = dist.size();
    // dp[mask][i] 表示已经访问的城市集合为mask，当前在城市i的最短路径
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
 
    // 起点为城市0
    dp[1][0] = 0; // 只访问城市0的状态
 
    for (int mask = 1; mask < (1 << n); mask++)
    {
        for (int i = 0; i < n; i++)
        {
            if ((mask >> i) & 1)
            { // 城市i已访问
                for (int j = 0; j < n; j++)
                {
                    if ((mask >> j) & 1 && i != j)
                    { // 城市j也已访问
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
                    }
                }
            }
        }
    }
 
    // 所有城市都访问并回到起点
    int result = INF;
    for (int i = 1; i < n; i++)
    {
        if (dist[i][0] != INF)
        {
            result = min(result, dp[(1 << n) - 1][i] + dist[i][0]);
        }
    }
 
    return result;
}
 
// --------------------- 数位DP ---------------------
 
// 计算区间[l,r]中满足条件的数字个数
int digitDP(int l, int r)
{
    vector<int> digits;
 
    // 数位分解函数
    auto getDigits = [&](int num)
    {
        vector<int> result;
        while (num)
        {
            result.push_back(num % 10);
            num /= 10;
        }
        reverse(result.begin(), result.end());
        return result;
    };
 
    // DP函数，自行定义状态和转移方程
    function<int(int, bool, bool, int)> dp = [&](int pos, bool isLimit, bool isNum, int state)
    {
        // 实现特定问题的状态转移逻辑
        // pos: 当前处理到的位置
        // isLimit: 是否有上界限制
        // isNum: 前面是否已经有数字了
        // state: 问题相关的状态
 
        if (pos == digits.size())
        {
            return isNum ? 1 : 0; // 根据具体问题调整返回值
        }
 
        // 这里补充具体问题的状态转移逻辑
 
        return 0; // 占位返回
    };
 
    // 计算[0,r]的结果
    digits = getDigits(r);
    int right_result = dp(0, true, false, 0);
 
    // 计算[0,l-1]的结果
    digits = getDigits(l - 1);
    int left_result = dp(0, true, false, 0);
 
    // 返回区间结果
    return right_result - left_result;
}
 
// --------------------- 概率DP ---------------------
 
// 骰子问题 - 投掷n个骰子，点数和为target的概率
double diceProb(int n, int target)
{
    if (target < n || target > 6 * n)
        return 0.0;
 
    vector<vector<double>> dp(n + 1, vector<double>(6 * n + 1, 0.0));
    // 初始化：一个骰子
    for (int i = 1; i <= 6; i++)
    {
        dp[1][i] = 1.0 / 6.0;
    }
 
    for (int i = 2; i <= n; i++)
    {
        for (int j = i; j <= 6 * i; j++)
        {
            for (int k = 1; k <= 6 && k < j; k++)
            {
                dp[i][j] += dp[i - 1][j - k] * (1.0 / 6.0);
            }
        }
    }
 
    return dp[n][target];
}
 
// --------------------- 实用DP子问题 ---------------------
 
// 最大子序和 (Kadane算法)
int maxSubArray(const vector<int> &nums)
{
    int currMax = nums[0], globalMax = nums[0];
 
    for (int i = 1; i < nums.size(); i++)
    {
        currMax = max(nums[i], currMax + nums[i]);
        globalMax = max(globalMax, currMax);
    }
 
    return globalMax;
}
 
// 最大子矩阵和
int maxSubMatrix(const vector<vector<int>> &matrix)
{
    if (matrix.empty() || matrix[0].empty())
        return 0;
 
    int rows = matrix.size(), cols = matrix[0].size();
    int result = INT_MIN;
 
    for (int left = 0; left < cols; left++)
    {
        vector<int> tempSum(rows, 0);
 
        for (int right = left; right < cols; right++)
        {
            // 将二维问题转化为一维
            for (int i = 0; i < rows; i++)
            {
                tempSum[i] += matrix[i][right];
            }
 
            // 应用Kadane算法找一维最大子序和
            int kadaneMax = tempSum[0];
            int currMax = tempSum[0];
 
            for (int i = 1; i < rows; i++)
            {
                currMax = max(tempSum[i], currMax + tempSum[i]);
                kadaneMax = max(kadaneMax, currMax);
            }
 
            result = max(result, kadaneMax);
        }
    }
 
    return result;
}
 
// 最长回文子串
string longestPalindrome(const string &s)
{
    int n = s.size();
    if (n == 0)
        return "";
 
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, maxLen = 1;
 
    // 所有长度为1的子串都是回文
    for (int i = 0; i < n; i++)
    {
        dp[i][i] = true;
    }
 
    // 检查长度为2的子串
    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            dp[i][i + 1] = true;
            start = i;
            maxLen = 2;
        }
    }
 
    // 检查长度大于2的子串
    for (int len = 3; len <= n; len++)
    {
        for (int i = 0; i <= n - len; i++)
        {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1])
            {
                dp[i][j] = true;
                start = i;
                maxLen = len;
            }
        }
    }
 
    return s.substr(start, maxLen);
}
// 很多DP end
 
// 拓扑
void solve()
{
    int n, m;
    cin >> n >> m;
    unordered_map<int, vector<int>> adj; // 邻接表
    vector<int> indegree(n, 0);          // 统计入度
    vector<int> result;                  // 结果集合
    int s, t;
    while (m--)
    {
        cin >> s >> t;
        indegree[t]++;
        adj[s].push_back(t);
    }
 
    queue<int> que;
    for (int i = 0; i < n; i++)
    {
        // 入度为0 可以作为开头 加入队列
        if (!indegree[i])
        {
            que.push(i);
        }
    }
 
    while (que.size())
    {
        auto cur = que.front();
        que.pop();
        result.push_back(cur);
 
        if (adj[cur].size())
        {
            for (auto &&i : adj[cur])
            {
                indegree[i]--;
                if (indegree[i] == 0)
                {
                    que.push(i);
                }
            }
        }
    }
    if (result.size() - n)
    {
        cout << -1;
    }
    else
    {
        cout << result;
    }
}
// 拓扑end
 
// 生成树 kru
void solve()
{
    int n, m;
    cin >> n >> m;
    struct Edge
    {
        int v1, v2, val;
        Edge(int v1, int v2, int val) : v1(v1), v2(v2), val(val) {};
    };
    vector<Edge> edges;
 
    int v1, v2, val;
    while (m--)
    {
        cin >> v1 >> v2 >> val;
        auto [a, b] = minmax(v1, v2);
        edges.emplace_back(a, b, val);
    }
    ranges::sort(edges, [](Edge &a, Edge &b)
                 { return a.val < b.val; });
 
    // FU begin
    vector<int> father;
    auto init = [&](int n)
    {
        father.resize(n + 1);
        iota(father.begin(), father.end(), 0ll);
    };
    function<int(int)> ffind = [&](int i)
    {
        return i == father[i] ? i : ffind(father[i]);
    };
    auto funion = [&](int i, int j)
    {
        auto ri = ffind(i), rj = ffind(j);
        if (ri != rj)
        {
            father[ri] = rj;
        }
    };
 
    auto issame = [&](int i, int j) -> bool
    {
        return ffind(i) == ffind(j);
    };
    // FU end
    init(n);
 
    int MSTweight = 0, MSTnode = 0;
 
    for (auto &&[v1, v2, val] : edges)
    {
        if (!issame(v1, v2))
        {
            funion(v1, v2);
            MSTweight += val;
            MSTnode++;
        }
        if (MSTnode == n - 1)
        {
            cout << MSTnode;
            return;
        }
    }
    cout << -1;
    return;
}
// 生成树 kru end
 
// 生成树 prim
void solve()
{
    int v, e;
    cin >> v >> e;
    int vsz = v + 1;
 
    vector<vector<pair<int, int>>> adj(vsz + 1);
    int v1, v2, val;
    while (e--)
    {
        cin >> v1 >> v2 >> val;
        adj[v1].emplace_back(v2, val);
        adj[v2].emplace_back(v1, val);
    }
 
    // prim begin
    vector<int> visited(vsz, 0), minDist(vsz, INFLL);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
 
    minDist[1] = 0;
    pq.push({0, 1});
 
    int totalweight = 0, nodeInMST = 0;
 
    while (pq.size())
    {
        auto [w, cur] = pq.top();
        pq.pop();
 
        if (visited[cur])
        {
            continue;
        }
 
        visited[cur] = 1;
        totalweight += w;
        nodeInMST++;
 
        for (auto &&[next, nextw] : adj[cur])
        {
            if (visited[next])
            {
                continue;
            }
 
            if (nextw < minDist[next])
            {
                minDist[next] = nextw;
                pq.push({minDist[next], next});
            }
        }
    }
    if (nodeInMST != v)
    {
        cout << -1;
        return;
    }
    cout << totalweight;
}
// prim end
 
// ford 可以处理负环
void solve()
{
    int n, m, s, t, v;
    cin >> n >> m;
    unordered_map<int, unordered_map<int, int>> adj;
    while (m--)
    {
        cin >> s >> t >> v;
        adj[s][t] = v;
    }
 
    vector<int> minDist(n + 1, INF);
    minDist[1] = 0;
 
    int _ = n - 1;
    while (_--) //
    {
        for (auto &&[v1, v] : adj)
        {
            for (auto &&[v2, val] : v)
            {
                if (minDist[v1] != INF)
                {
                    minDist[v2] = min(minDist[v2], minDist[v1] + val);
                }
            }
        }
    }
 
    if (minDist[n] == INF)
    {
        cout << "unconnected";
    }
    else
    {
        cout << minDist[n];
    }
}
// ford end
 
// dijk
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1); // 邻接表，pair<节点, 距离>
    int s, e, v;
    while (m--)
    {
        cin >> s >> e >> v;
        adj[s].push_back({e, v});
    }
 
    /*
    堆优化版Dijkstra算法:
    1. 使用优先队列维护当前所有可达但未访问的节点，按距离排序
    2. 每次取出队列中距离最小的节点，标记为已访问
    3. 更新该节点邻居的距离，并将新的可能路径加入队列
    */
 
    vector<int> minDist(n + 1, INT_MAX); // 每一个节点到源点的最小距离
    vector<bool> visited(n + 1, false);  // 记录节点是否已被访问
 
    int start = 1, en = n;
    minDist[start] = 0;
 
    // 优先队列，存储<距离, 节点编号>，按距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
 
    while (!pq.empty())
    {
        int dist = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
 
        if (visited[cur])
            continue;        // 如果已经访问过，跳过
        visited[cur] = true; // 标记为已访问
 
        // 更新当前节点的所有邻居
        for (const auto &edge : adj[cur])
        {
            int next = edge.first;
            int weight = edge.second;
 
            if (!visited[next] && minDist[cur] + weight < minDist[next])
            {
                minDist[next] = minDist[cur] + weight;
                pq.push({minDist[next], next});
            }
        }
    }
 
    cout << (minDist[en] == INT_MAX ? -1 : minDist[en]);
}
// dijk end
 
// 多源最短路 floyd
void solve()
{
    int n;
    cin >> n;
    vector v(n + 1, vector<int>(n + 1, INT_MAX));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> v[i][j];
        }
    }
 
    // floyd
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
            }
        }
    }
}
// flyd end