//这题Gao死我了！！！

Gao

题意：Gao这个函数可以用来算出有向图中从0到达某点的最短路径条数，用Gao算出0到所有点的最短路径条数了，现问有多少条路径经过点v。输出答案的后10位。

解析：首先，这题有10000个点50000条边，对每点求最短路径是不可能的。观察最短路径以后我们可以知道，一个点v在一条最短路径里最多出现1次，要么出现在路径的末尾，要么出现在路径的中间，对于出现在末尾的最短路径数我们定义为cnt1[v]，而我们在计算0点到所有点的最短路径过程中是可以记录cnt1[v]的：

if(dis[u]+w<dis[v])                  //u->v权值为w
{
	dis[v]=dis[u]+w;
	cnt1[v]=cnt1[u];
	tmp.v=v;tmp.dis=dis[v];
	que.push(tmp);
}
else if(dis[u]+w==dis[v])
{	cnt1[v]+=cnt1[u];
	cnt1[v]%=MOD;
}

至于v出现在最短路径的中间的情况，定义cnt2[v]表示最短路径中从v出发的路径条数，那么根据组合数学定义,v出现在最短路中间的最短路径条数=cnt1[v]*cnt2[v]。cnt2[v]可以用Calc(v)进行递归计算(貌似也可以叫树形DP,好像还可以拓扑排序以后之间DP），假如有t1,t2,t3...tn与v邻接且v->t1,v->t2,v->t3...,v->tn都在最短路径上，那么同样根据组合数学加法原理有cnt2[v]=cnt2[t1]+cnt2[t2]+...cnt[tn]。因为t1,t2,tn都在最短路径上，所以cnt2[v]+=n;

最终ans[v]=cnt1[v]+cnt1[v]*cnt2[v]。

这题比较阴险的地方在于答案要保留后10位，而进行乘法的过程中会超long long（事实证明，在计算cnt1的过程中也会超long long，在这地方无限WA T_T）要用到布斯(Booth)乘法：

long long Mul(long long lhs,long long rhs)
{
	long long lhs2=lhs%100000;
	long long rhs2=rhs%100000;
	return ((lhs/100000*rhs2+rhs/100000*lhs2)*100000+lhs2*rhs2)%MOD;
}

最后贴一个完整的代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const long long MOD=10000000000LL;

struct Edge
{
	int v,next,w;
}buf[50010];

struct Node
{
	int v,dis;
};

const int INF=1<<30;

bool operator<(Node a,Node b)
{
	return a.dis>b.dis;
}

int head[10010];
int dis[10010];
long long cnt[10010];
bool flag[10010];
int N,M,nE,Q;

void addEdge(int u,int v,int w)
{
	buf[nE].v=v;buf[nE].w=w;buf[nE].next=head[u];head[u]=nE++;
}

long long Mul(long long lhs,long long rhs)
{
	long long lhs2=lhs%100000;
	long long rhs2=rhs%100000;
	return ((lhs/100000*rhs2+rhs/100000*lhs2)*100000+lhs2*rhs2)%MOD;
}

long long add(long long a,long long b)
{
	a+=b;
	if(a>=MOD)
		a-=MOD;
	return a;
}

void Dijkstra(int src)
{
	Node tmp,cur;
	tmp.v=src;tmp.dis=0;
	for(int i=0;i<=N;i++)
		dis[i]=INF;
	dis[src]=0;

	memset(flag,false,sizeof(flag));
	memset(cnt,0,sizeof(cnt));
	priority_queue<Node> que;
	cnt[src]=1;
	que.push(tmp);
	while(!que.empty())
	{
		cur=que.top();que.pop();
		int u=cur.v,d=cur.dis;
		if(flag[u])continue;
		flag[u]=true;
		for(int i=head[u];i!=-1;i=buf[i].next)
		{
			int v=buf[i].v,w=buf[i].w;
			if(d+w<dis[v])
			{
				dis[v]=d+w;
				cnt[v]=cnt[u];
				tmp.v=v;tmp.dis=dis[v];
				que.push(tmp);
			}
			else if(d+w==dis[v])
			{	cnt[v]+=cnt[u];
				cnt[v]%=MOD;
			}
		}
	}
}

long long rec[10010];

long long Gao(int s)
{
	long long c=0;
	if(rec[s]!=-1)return rec[s];
	for(int i=head[s];i!=-1;i=buf[i].next)
	{
		int v=buf[i].v;
		if(dis[s]+buf[i].w==dis[v]&&s!=v)
		{
			c++;
			if(rec[v]==-1)
				rec[v]=Gao(v);
			c=add(c,rec[v]);
		}
	}
	return c%MOD;
}

int main()
{
	//freopen("data","r",stdin);
	//freopen("mout","w",stdout);
	while(scanf("%d%d%d",&N,&M,&Q)!=EOF)
	{
		memset(head,0xff,sizeof(head));
		memset(rec,0xff,sizeof(rec));
		nE=0;
		while(M--)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			addEdge(u,v,w);
		}
		Dijkstra(0);
		int q;
		while(Q--)
		{
			scanf("%d",&q);
			if(cnt[q]<0)while(1);
			long long ans=Mul(cnt[q],Gao(q)+1);
			ans=ans%MOD;
			printf("%010lld\n",ans);
		}
		//putchar(10);
	}
	return 0;
}

• 相关文章