题意

    给一张边数为 m m m，点数为 n n n的无向图（并不一定连通）。题目给了一种特定的走法。

• 每次只能走两条边。现在命这两条边的权值分别为 d i s a dis_a disa​和 d i s b dis_b disb​。我们经过这两天边需要的权值为 （ d i s a + d i s b ） ∗ （ d i s a + d i s b ） （dis_a + dis_b） * （dis_a + dis_b） （disa​+disb​）∗（disa​+disb​）

    问从1出发到达每个点需要的最小权值分别为多少。

题解

    注意题目中，每条边的权值给定的范围是 [ 1 , 50 ] [1,50] [1,50]。因此我们可以在 D i j k s t r a Dijkstra Dijkstra算法的标记数组 v i s [ N ] vis[N] vis[N]的基础上，将其改进为 v i s [ 51 ] [ N ] vis[51][N] vis[51][N]，通式为 v i s [ d i s ] [ u ] vis[dis][u] vis[dis][u]。即记录是否通过权值为 d i s dis dis的边到达点 u u u。 d i s [ 51 ] [ N ] dis[51][N] dis[51][N]同理，即表示通过权值为 d i s dis dis的边到达点 u u u花费的权值是多少。
    由于题目一次要连续走两步，而该题数据量有 1 e 5 1e5 1e5，显然通过二重循环达到一次走两步的方法的复杂度是不可行的。这时候就需要巧妙地运用上面改进的两个变量了。
    当我们走了奇数条边的时候，显然这个时候转移才进行到一半，我们需要将走过的边的权值和总权值都记录下来，以便下一次处理。
    当我们走了偶数条边的时候，说明已经到达了目标点，那我们就通过之前记录的信息计算出到达当前点花费的权值。
    具体内容参照代码。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define lowbit(x) ((x) & -(x))
#define endl "\n"
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 10, NN = 5e1 + 10, INF = 0x3f3f3f3f, LEN = 20;
const ll MOD = 1e9 + 7;
const ull seed = 31;
const double pi = acos(-1.0), eps = 1e-8;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
struct Edge {
    int next, to, dis;
} edge[N];
struct Node {
    int id, dis, pre;
    Node(int id, int dis, int pre) : id(id), dis(dis), pre(pre) {}
    bool friend operator<(const Node& a, const Node& b) {
        return a.dis > b.dis;
    }
};
int n, m, num_edge;
int head[N];
int dis[NN][N];
bool vis[NN][N];
void add_edge(int from, int to, int dis) {
    edge[num_edge].next = head[from];
    edge[num_edge].to = to;
    edge[num_edge].dis = dis;
    head[from] = num_edge++;
}
void dijkstra() {
    priority_queue<Node> q;
    memset(dis, INF, sizeof dis);
    dis[0][1] = 0;
    q.push(Node(1, 0, 0));
    while (!q.empty()) {
        Node u = q.top();
        q.pop();
        if (vis[u.pre][u.id])
            continue;
        vis[u.pre][u.id] = true;
        for (int i = head[u.id]; i != -1; i = edge[i].next) {
            Edge v = edge[i];
            if (u.pre == 0) {
                if (u.dis + v.dis < dis[v.dis][v.to]) { // 此时走过奇数条边
                    dis[v.dis][v.to] = u.dis + v.dis;
                    q.push(Node(v.to, u.dis + v.dis, v.dis));
                }
            } else {
                // 此时走过偶数条边
                ll Dist = u.dis - u.pre + (v.dis + u.pre) * (v.dis + u.pre);
                // u.dis要减去u.pre的原因是在73行，为了方便，暂时将u.pre累加进了总权值
                // 而其实u.pre是要通过和v.dis的计算才能正式进入总权值的
                if (Dist < dis[0][v.to]) {
                    dis[0][v.to] = Dist;
                    q.push(Node(v.to, Dist, 0));
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (dis[0][i] == INF)
            printf("-1 ");
        else
            printf("%d ", dis[0][i]);
    }
}
void init() {
    num_edge = 0;
    memset(head, -1, sizeof head);
}
int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    n = read();
    m = read();
    init();
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        u = read();
        v = read();
        w = read();
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dijkstra();
    return 0;
}