void Dijkstra (int s) { // dist[i] is the minimum distance from s to i // num[i] is the number of shortest paths from s to i for (int i=1; i<=n; i++) { dist[i]=inf; num[i]=0; } dist[s]=0; priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq; pq.push({0,s}); num[s]=1; while (!pq.empty()) { pair<int,int> tmp=pq.top(); pq.pop(); int u=tmp.second; for (auto g:adj[u]) { // v is the adjacent vertex with u // w is the weight of the edge u-v int v=g.second; int w=g.first; if (dist[v]==dist[u]+w) { num[v]+=num[u]; } if (dist[v]>dist[u]+w) { dist[v]=dist[u]+w; num[v]=num[u]; pq.push({dist[v],v}); } } } }