这个题我用了n次的dij

然后#2被卡了

数据大概长许多个菱形首尾相接成一条长链

然后我往回找时就要找2^n次（就是那个check函数）

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int N=110;
struct person{
	ll who,num;
	bool operator <(const person &B)const
	{
		return num>B.num;
	}
};
priority_queue<person> que;
int n,m;
int a[N][N],vis[N];
ll ans[N],cnt[N];
double ve[N];
void dij(int st)
{
	ans[st]=0;
	cnt[st]=1;
	person q,qq;
	q.who=st;
	q.num=0;
	que.push(q);
	while(!que.empty())
	{
		q=que.top();
		que.pop();
		if(vis[q.who])
		 continue;
		vis[q.who]=1;
		for(int i=1;i<=n;i++)
		{
			if(a[q.who][i]!=0&&ans[q.who]+a[q.who][i]==ans[i])
			{
				cnt[i]+=cnt[q.who];
				continue;
			}
			if(a[q.who][i]!=0&&ans[q.who]+a[q.who][i]<ans[i])
			{
				cnt[i]=cnt[q.who];
				ans[i]=ans[q.who]+a[q.who][i];
				qq.who=i;
				qq.num=ans[i];
				que.push(qq);
			}
		}
	}
}
void check(int st,int now,int cst)
{//////////
	for(int i=1;i<=n;i++)
	{
		if(ans[now]-a[now][i]==ans[i]&&a[now][i]!=0&&i!=st)
		{
			ve[i]+=cnt[i]*1.0/cst;
			check(st,i,cst);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		a[u][v]=w;
		a[v][u]=w;
	}
	for(int i=1;i<=n;i++)
	{
		memset(ans,0x3f,sizeof(ans));
		memset(vis,0,sizeof(vis));
		memset(cnt,0,sizeof(cnt));
		while(!que.empty())que.pop();
		dij(i);
		for(int j=1;j<=n;j++)
		{
			if(i!=j)
			 check(i,j,cnt[j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%.3f\n",ve[i]);
	}
}