题目大意
CF1486E Paired Payment
单源最短路，但是距离计算的规则是每两条边权值之和的平方,两两一组。例如：分别走过 5,3,11,6 四条边，权值有两组，距离计算是 (5+3)^2+(11+6)^2=353。
做法
考虑类似分层图的思想。题目有一个很友善的数据范围：边权 w\le50。所以可以设数组 \texttt{dis[200005][51]}，其中 \texttt{dis[i][j]} 表示走到 i 号点，上一条边的边权是 j 的最短路程。特别地，j=0 时，表示接下来是一组新的边。
$j=0$ 时，此时上一条边已经在前面的组合里了，随便选一条边作为新的组合，先不更新权值。
其他的和最短路差别不大，具体见代码。
## 代码
```cpp
/*
Luogu CF1486E Paired Payment
https://www.luogu.com.cn/problem/CF1486E
*/
#include "iostream"
#include "queue"
#include "cstring"
using namespace std;
const int N=200005;
int n, m, head[N], idx, temp1, temp2, temp3;
int dis[N][51];
bool ins[N][51];
struct edge{
int to, nxt, w;
}e[2*N];
struct node{
int id, pre;
node(int id=1, int pre=0){
this->id=id;
this->pre=pre;
}
};
void add_edge(int u, int v, int w){
e[++idx].to=v;
e[idx].w=w;
e[idx].nxt=head[u];
head[u]=idx;
}
int square(int i){
return i*i;
}
void spfa(){
queue<node>q;
q.push(node(1, 0));
memset(dis, 0x3f, sizeof(dis));
dis[1][0]=0;
while(!q.empty()){
int id=q.front().id, pre=q.front().pre;
ins[id][pre]=false;
q.pop();
if(pre==0){
for(int i=head[id];i;i=e[i].nxt){
int to=e[i].to, w=e[i].w;
if(dis[id][0] < dis[to][w]){
dis[to][w] = dis[id][0];
if(!ins[to][w]){
ins[to][w]=true;
q.push(node(to, w));
}
}
}
}else{
for(int i=head[id];i;i=e[i].nxt){
int to=e[i].to, w=e[i].w;
if(dis[id][pre]+square(pre+w)<dis[to][0]){
dis[to][0]=dis[id][pre]+square(pre+w);
if(!ins[to][0]){
ins[to][0]=true;
q.push(node(to, 0));
}
}
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i=1;i<=m;i++){
cin >> temp1 >> temp2 >> temp3;
add_edge(temp1, temp2, temp3);
add_edge(temp2, temp1, temp3);
}
spfa();
for(int i=1;i<=n;i++) cout << (dis[i][0]==0x3f3f3f3f ? -1 : dis[i][0]) << " ";
}
```