题目还算不难吧
首先我们枚举点$i$，将其他所有点到这个点的最短路求出来
然后我们在这一次建出的最短路$DAG$的反图上进行拓扑排序。假设我们算到了点$j$，点$j$的人流量为$t_j$，点$j$连出去的边到达的点为点集$\{v\}$，那么对于每一个点$u \in \{v\}$，边$(j,u)$的流量就会增加$\frac{t_j}{|\{v\}|}$，$t_u$会加上$\frac{t_j}{|\{v\}|}$
总时间复杂度$O(N^2)$
#include<bits/stdc++.h> #define ld long double using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); ) + (a << ) + (c ^ ') , c = getchar(); return a; } inline int max(int a , int b){ return a > b ? a : b; } struct Ed{ int start , end , upEd; }ans[]; ] , ifRail[][]; ]; ] , minRoute[]; ld peo[][] , To[][]; struct cmp{ bool operator() (const int& a, const int& b ){ return minRoute[a] < minRoute[b]; } }; int main(){ int N = read() , M = read(); ; i <= M ; i++){ int a = read() , b = read(); ans[(i << ) - ].start = a; ans[(i << ) - ].end = b; ans[(i << ) - ].upEd = firEd[a]; firEd[a] = (i << ) - ; ans[i << ].start = b; ans[i << ].end = a; ans[i << ].upEd = firEd[b]; firEd[b] = i << ; ifRail[a][b] = ifRail[b][a] = ; } ; i <= N ; i++) ; j <= N ; j++) To[i][j] = read(); ; i <= N ; i++){ memset(minRoute , 0x3f , sizeof(minRoute)); memset(Times , , sizeof(Times)); minRoute[i] = ; Times[i] = ; queue < int > q; priority_queue < int , vector < int > , cmp > q1; q.push(i); while(!q.empty()){ int t = q.front(); q.pop(); ; for(int j = firEd[t] ; j ; j = ans[j].upEd) ){ minRoute[ans[j].end] = minRoute[t] + ; Times[ans[j].end] = Times[t]; q.push(ans[j].end); f = ; } ){ Times[ans[j].end] += Times[t]; f = ; } if(!f) q1.push(t); } memset(vis , , sizeof(vis)); vis[i] = ; while(!q1.empty()){ int t = q1.top(); q1.pop(); ; j <= N ; j++) ){ ld t1 = (ld)To[i][t] * Times[j] / Times[t]; peo[j][t] += t1; peo[t][j] += t1; To[i][j] += t1; if(!vis[j]){ vis[j] = ; q1.push(j); } } } } ; i <= M ; i++) cout << ) << peo[ans[i << ].start][ans[i << ].end] + 1e- << endl; ; }
