题解：CF1486E Paired Payment

首先我们可以考虑对于任意连续两点进行连边，但很明显，这会被菊花图卡掉。
思考如果我们将状态从 dis_i 改为 dis_{i,j} 代表以 j 为中间点到 i 的最短路。然而这也会超时，不过我们注意到了 w\le50。
所以我们定义状态 dis_{i,j} 代表从长度为 j 的边到达 i 的最短距离，若此时走了偶数次，j=0。
对于一条从 x 到 y 的，长度为 z 的边，若已走偶数步：

若已走奇数步：

其中 las 为上一条边的长度。
最后，到点 i 的答案为 dis_{i,0}。
注：
由于路径可能有重复经过的点，所以去掉判重复经过的部分。此时 dijkstra 在使用大根堆时的答案也是正确的，只不过会超时。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,z,dis[100010][60];
bool vis[100010][60];
vector<pair<int,int>>e[100010];
struct node{int u,fr,dis;};
bool operator < (node x,node y){return x.dis>y.dis;}
priority_queue<node>q;
void dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    q.push({1,0,0});
    dis[1][0]=0;
    while(q.size())
    {
        int u=q.top().u,fr=q.top().fr;
        q.pop();
//      if(vis[u][fr])continue;
//      vis[u][fr]=1;
        for(auto i:e[u])
        {
            if(fr)
            {
                if(dis[i.first][0]>dis[u][fr]+(i.second*fr*2)+(i.second*i.second))
                {
                    dis[i.first][0]=dis[u][fr]+(i.second*fr*2)+(i.second*i.second);
                    q.push({i.first,0,dis[i.first][0]});
                }
            }
            else
            {
                if(dis[i.first][i.second]>dis[u][0]+i.second*i.second)
                {
                    dis[i.first][i.second]=dis[u][0]+i.second*i.second;
                    q.push({i.first,i.second,dis[i.first][i.second]});
                }
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>x>>y>>z,e[x].push_back({y,z}),e[y].push_back({x,z});
    dijkstra();
    for(int i=1;i<=n;i++)cout<<(dis[i][0]!=0x3f3f3f3f3f3f3f3f?dis[i][0]:-1)<<' ';
    return 0;
}