自动搬运

查看原文

来自洛谷，原作者为

	lgswdn_SA 舞台少女，每日进化中

搬运于2025-08-24 22:15:14，当前版本为作者最后更新于2021-04-24 22:43:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$$\begin{aligned} R(v)&=\sum_{s}\sum_{t}\frac{a_sa_t\sigma_{st}(v)}{\sigma_{st}}\\ &=\sum_s a_s \sum_t \frac{a_t \sigma_{sv}\sigma_{vt}}{\sigma_{st}}\\ &= \sum_s a_s \sigma_{sv} \sum_t \frac{a_t\sigma_{tv}}{\sigma_{st}} \end{aligned} $$

考虑用计算贡献的方法做。

$$R(v) \leftarrow a_s \sigma_{sv} \sum_t \frac{a_t\sigma_{tv}}{\sigma_{st}} $$

对于每一个点 $s$，建出以其为源点的最短路 DAG （将边反向，因为 DP 的顺序为拓扑逆序），然后 DAG 上 DP。$\sigma$ 在求最短路的时候就能算。设 $f_u=\sum_t\frac{a_t\sigma_{tv}}{\sigma_{st}}$。转移为将 $\sigma_{u,t}=\sigma_{u,v}\times \sigma_{v,t}$ ：

$$f_u=\frac{a_u}{\sigma_{su}}+\sum_{v\to u} f_vw_{uv} $$

要注意，$f$ 包含 $u=t$ 的情况，于是答案需要忽略这种情况。

#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1009, M=5009;
typedef pair<int,int> pii;

inline long long read() {
    register long long x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

struct edge {int to,nxt,w; double wd;} e[M*2]; int hd[N],tot=1;
void add(int u,int v,int w,double wd) {e[++tot]=(edge){v,hd[u],w,wd};hd[u]=tot;}

int n,m,d[N],deg[N],a[N];
long double sig[N],f[N],ans[N];
bool vst[N];
vector<edge>dag[N];

void dijkstra(int s) {
	priority_queue<pii>q; q.push(make_pair(0,s));
	memset(d,0x3f,sizeof(d)), memset(vst,0,sizeof(vst));
	d[s]=0, sig[s]=1;
	while(!q.empty()) {
		int u=q.top().second; q.pop();
		if(vst[u]) continue; vst[u]=1;
		for(int i=hd[u],v;i;i=e[i].nxt) {
			if(d[v=e[i].to]>d[u]+e[i].w)
				d[v]=d[u]+e[i].w, q.push(make_pair(-d[v],v)), sig[v]=sig[u]*e[i].wd;
			else if(d[v]==d[u]+e[i].w) sig[v]+=sig[u]*e[i].wd;
		}
	}
}
void topo(int s) {
	queue<int>q; memset(f,0,sizeof(f));
	rep(i,1,n) if(!deg[i]) q.push(i);
	while(!q.empty()) {
		int u=q.front(); q.pop();
		ans[u]+=a[s]*sig[u]*f[u], f[u]+=a[u]/sig[u];
		for(auto ed:dag[u]) {
			int v=ed.to; double wd=ed.wd;
			f[v]+=f[u]*wd, deg[v]--;
			if(!deg[v]) q.push(v);
		}
	}
}

int main() {
	n=read(), m=read();
	rep(i,1,n) a[i]=read();
	rep(i,1,m) {
		int u,v,w; double wd; scanf("%d%d%d%lf",&u,&v,&w,&wd);
		add(u,v,w,wd), add(v,u,w,wd);
	}
	rep(s,1,n) {
		dijkstra(s); sig[s]=0;
		rep(u,1,n) for(int i=hd[u],v;i;i=e[i].nxt) if(d[u]+e[i].w==d[v=e[i].to])
			dag[v].push_back(e[i^1]), deg[u]++;
		topo(s);
		rep(u,1,n) dag[u].clear();
	}
	rep(i,1,n) printf("%.6Lf\n",ans[i]);
	return 0;
}