本文主要是介绍codeforces（E. Paired Payment）（dijkstra 多维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
inline int read() {char c = getchar(); int x = 0, f = 1;while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}return x * f;
}
using namespace std;int n,m,inf=0x3f3f3f3f;
int dis[100005][51][3];
bool vis[100005][51][3];
vector<pair<int,int>> edg[100005];
int ans[100005];
struct node
{int x,pw,eo,val;bool operator <(const node &a)const{return a.val<val;}
};
priority_queue<node> q;
void dijkstra()
{memset(dis,inf,sizeof(dis));for(int i=0;i<51;i++){vis[1][i][0]=1;}vis[1][0][0]=0;dis[1][0][0]=0;dis[1][0][1]=0;q.push({1,0,0,0});while(!q.empty()){node u=q.top();q.pop();if(vis[u.x][u.pw][u.eo]!=0){continue;}vis[u.x][u.pw][u.eo]=1;for(int i=0;i<edg[u.x].size();i++){int v=edg[u.x][i].first;int kk=0;if(u.eo==1){kk=(u.pw+edg[u.x][i].second)*(u.pw+edg[u.x][i].second);}if(dis[v][edg[u.x][i].second][u.eo^1]>dis[u.x][u.pw][u.eo]+kk){dis[v][edg[u.x][i].second][u.eo^1]=dis[u.x][u.pw][u.eo]+kk;q.push({v,edg[u.x][i].second,u.eo^1,dis[v][edg[u.x][i].second][u.eo^1]});}}}
}
int main()
{n=read();m=read();for(int i=1;i<=m;i++){int x,y,z;x=read();y=read();z=read();edg[x].pb({y,z});edg[y].pb({x,z});}dijkstra();memset(ans,inf,sizeof(ans));for(int i=1;i<=n;i++){bool flag=0;for(int j=0;j<51;j++){if(vis[i][j][0]!=0){ans[i]=min(ans[i],dis[i][j][0]);flag=1;}}if(flag){printf("%d ",ans[i]);}else{printf("-1 ");}}printf("\n");return 0;
}这篇关于codeforces（E. Paired Payment）（dijkstra 多维）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
