题目描述

Z-Kingdom有着四通八达的现代化交通。时值独立庆典之际,随着来自周边国家旅客的日益增多,犯罪行为也悄无声息开始滋长起来。

特别任务支援科的警察们从总部收到了关于调查伪装在游客中的犯罪分子的请求。通过调查,他们得到了一张地图,记载了Z-Kingdom内每一条道路的长度。

显然,为了减少犯罪行为被发现的可能性,犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线,他们希望得知任意两个地点之间,有多少条犯罪分子可能会选择的道路。

输入输出格式

输入格式:

第一行,包含两个整数N,M,表示Z-Kingdom内的地点数和道路数。

接下来N行,每行包含三个整数x,y,z,表示道路连接的两个不同地点的标号,以及道路的长度。道路是双向的。

两个不同地点之间不会有超过一条道路。

输出格式:

输出一行,包含 N (N-1)/2 个整数

其中表示 x 号地点到 y 号地点之间有多少条犯罪分子可能会选择的道路。

先Floyd求出最短路

对于每一个点i:

{

枚举所有点j ,确保i,j联通,且i,j不是一点。

然后检查有多少点k与j有连边,且在i-j的最短路disi,j上。(也就是检查从i到j有多少条满足disi,j上且与j相连

       esumj=∑k1     k∈(g[k][j]!=0 && dis[i][k]+g[k][j]==dis[i][j])

最后考虑DP

枚举一个终点j,再枚举一个k,如果k在i-j的最短路上,那么esum[k]个方案计入C[i][j]。(有esumk条边可以到k点,在最短路上可以选k点,所以要计入方案数目)

}

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<utility>
#include<queue>
using namespace std;

int nodenum,edgenum;
int g[510][510]={0},dis[510][510]={0},fx,wx,tx,C[510][510]={0};
int esum[510]={0};

inline void readx(int& x)
{
	x=0;
	register char ch=0; int k=1;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

void SPFA(int nodex)
{
	bool vis[510]={0};
	register int prex,u,v;
	queue<int> que;

	vis[nodex]=true; dis[nodex][nodex]=0; que.push(nodex);
	while (!que.empty())
	{
		u=que.front(); que.pop();
		vis[u]=false;
		for (register int i=1;i<=nodenum;i++) if (g[u][i])
		{
			if (dis[nodex][i]>dis[nodex][u]+g[u][i])
			{
				dis[nodex][i]=dis[nodex][u]+g[u][i];
				if (!vis[i])
				{
					que.push(i);
					vis[i]=true;
				}
			}
		}
	}
}

int main()
{
	memset(dis,0x3f,sizeof(dis));
	readx(nodenum); readx(edgenum);
	for (register int i=1;i<=edgenum;i++)
	{
		readx(fx); readx(tx); readx(wx);
		g[fx][tx]=g[tx][fx]=wx;
	}
	
	for (register int i=1;i<=nodenum;i++) SPFA(i);
	
	//init
	for (register int i=1;i<=nodenum;i++)
	{
		memset(esum,0,sizeof(esum));
		for (register int j=1;j<=nodenum;j++) if (i!=j && dis[i][j]!=dis[0][0])
		{
			for (register int k=1;k<=nodenum;k++) if (g[k][j])
			{
				if (dis[i][k]+g[k][j]==dis[i][j]) esum[j]++;
			}
		}
		for (register int j=1;j<=nodenum;j++) if (i!=j)
		{
			for (register int k=1;k<=nodenum;k++) if (i!=k)
			{
				if (dis[i][k]+dis[k][j]==dis[i][j]) C[i][j]+=esum[k];
			}
		}
	}
	
	for (register int i=1;i<=nodenum;i++)
		for (register int j=i+1;j<=nodenum;j++) printf("%d ",C[i][j]);
	
	return 0;
}
分类: DPFloyd

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.