Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.4 kB
3
Indexable
Never
#include <bits/stdc++.h>// talvez inverter para dist[maxn][53],criar um vetor de visitados
using namespace std;
typedef long long int ll;
typedef pair<ll,ll>ii;
typedef pair<ll,ii>iii;
const int maxn=1e5+2;
#define pb push_back

vector<ii>adj[maxn];
ll n,m;
ll dist[maxn][53];//menor dist pegando a aresta i para o vertice j;
bool vis[maxn][53];

void dijkstra(){
	priority_queue<iii,vector<iii>,greater<iii>> fila;//armazena dist total, de qual aresta veio, e vertice
	dist[1][0]=0;
	fila.push({0,{0,1}});

	while(!fila.empty()){
		ll custo=fila.top().first,edge=fila.top().second.first,x=fila.top().second.second;
		fila.pop();


		if(vis[x][edge])continue;
		vis[x][edge] = 1;

		for(int i=0; i<adj[x].size(); i++){
			int xx=adj[x][i].first,c=adj[x][i].second;

			if(edge==0){
				if(dist[xx][c]!=-1 and dist[xx][c]<custo)continue;
				dist[xx][c]=custo;
				fila.push({custo,{c,xx}});
			}
			else{
				ll novo=(edge+c)*(edge+c);
				novo+=custo;
				if(dist[xx][0]!=-1 and dist[xx][0]<novo)continue;
				dist[xx][0]=novo;
				fila.push({novo,{0,xx}});
			}
		}
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n>> m;
	memset(dist,-1,sizeof(dist));

	for(int i=0; i<m; i++){
		ll a,b,c;cin>>a>>b>>c;
		adj[a].pb({b,c});
		adj[b].pb({a,c});
	}
	dijkstra();

	for(int i=1; i<=n; i++){
		if(i!=1)cout<<' ';
		cout<< dist[i][0];
	}
	cout<<endl;
	return 0;

}