1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| const int N=100010; const int M=400010; const int K=52; const ll inf=1e18; int n,m; int ver[M],val[M],head[N],ne[M],tot; inline void add(int x,int y,int z) { ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot; ver[++tot]=x; val[tot]=z; ne[tot]=head[y]; head[y]=tot; } ll f[N][K]; bool vis[N][K]; struct node{ int x,y; ll d; friend inline bool operator<(const node &A,const node &B) { return A.d>B.d; } }; priority_queue<node> q; int main() { n=read(); m=read(); int x,y,z; fo(i,1,m) x=read(),y=read(),z=read(),add(x,y,z); fo(i,1,n) fo(j,0,50) f[i][j]=inf; f[1][0]=0; q.push((node){1,0,0}); for(;!q.empty();) { node u=q.top(); q.pop(); if(vis[u.x][u.y]) continue; vis[u.x][u.y]=1; if(!u.y) { for(int i=head[u.x],v;i;i=ne[i]) { v=ver[i]; if(f[v][val[i]]>f[u.x][0]) { f[v][val[i]]=f[u.x][0]; q.push((node){v,val[i],f[u.x][0]}); } } } else { for(int i=head[u.x],v;i;i=ne[i]) { v=ver[i]; if(f[v][0]>f[u.x][u.y]+(u.y+val[i])*(u.y+val[i])) { f[v][0]=f[u.x][u.y]+(u.y+val[i])*(u.y+val[i]); q.push((node){v,0,f[v][0]}); } } } }
ll ans; fo(i,1,n) { if(f[i][0]==inf) f[i][0]=-1; printf("%lld ",f[i][0]); } return 0; }
|