跑n次
void dijk(){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]= inf; priority_queue<pii,vector<pii>,greater<pii> >q; for(int S=1;S<=n;S++){ q.push(pii(0,S)); for(int i=1;i<=n;i++) vis[i] =0 ; d[S][S]=0; while(q.empty()==0){ int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(auto &[y,z]:g[x]) if(d[S][x]+z<d[S][y]){ d[S][y]=d[S][x]+z; q.push(pii(d[S][y],y)); } } } }