# 131 条题解

• @ 2017-04-27 13:24:23

Floyd

``````#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 110, INF = 0x3f3f3f3f;
int dis[maxn][maxn];

int print(int u, int v, int n) {
int _count = 2;
for (int i = 1; i <= n; i++)
if (u != i && v != i && dis[u][v] == dis[u][i] + dis[i][v])
_count++;
return _count;
}

int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
dis[i][j] = INF;
while (m--) {
int u, v;
cin >> u >> v;
dis[u][v] = dis[v][u] = 1;
}
// Floyd
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && j != k && i != k)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int q;
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
cout << print(u, v, n) << endl;
}
return 0;
}
``````
• @ 2017-05-30 17:21:00
``````#include<stdio.h>
#include<string.h>
int n,m,p,s[1010][1010];
int c(int x,int y,int z=0){
for(int i=1;i<=n;++i) if(s[x][i]+s[i][y]==s[x][y]) z++;
return z;
}
int main(){
scanf("%d%d",&n,&m);
memset(s,1,sizeof s);
for(int i=1;i<=n;++i) s[i][i]=0;
for(int x,y,i=0;i<m;++i){
scanf("%d%d",&x,&y);
s[x][y]=1; s[y][x]=1;
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(s[i][j]>s[i][k]+s[k][j]) s[i][j]=s[i][k]+s[k][j];
scanf("%d",&p);
for(int x,y,i=0;i<p;++i){
scanf("%d%d",&x,&y);
printf("%d\n",c(x,y));
}
}
``````
• @ 2018-08-11 11:09:06

floyd
ovo！！！

``````#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int f[110][110],n,m,a1,b1,a2,b2,ans,p;
int ovo(int u,int v,int n1)
{
int sum=2;
for(int i=1;i<=n;i++)
{
if(u!=i&&v!=i&&f[u][v]==f[u][i]+f[i][v])
{
sum++;
}
}
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)f[i][j]=0x3f;
}
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a1,&b1);
f[a1][b1]=1;
f[b1][a1]=1;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(f[i][k]+f[k][j]<f[i][j])f[i][j]=f[i][k]+f[k][j];
}
}
}
scanf("%d",&p);
for(int i=p;i>=1;i--)
{
scanf("%d%d",&a2,&b2);
ans=ovo(a2,b2,n);
printf("%d\n",ans);
}
return 0;
* }
``````
• @ 2012-10-15 15:37:16

FLOYED解决之。注意题目，只要是满足是在最短路上的点都可以计入答案。

http://hi.baidu.com/samroxas/item/18e3dcf260386b1ce2e3bd1f

• @ 2019-02-11 15:50:42

#include<cmath>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int n,m,a[101][101],p;
int ans(int x,int y)
{
int q;
q=0;
for(int i=1;i<=n;i++)
if(a[x][i]+a[i][y]==a[x][y])
q++;
return q;
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
memset(a,0x3f,sizeof(a));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x][y]=1;
a[y][x]=1;
}
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][j]>a[i][k]+a[k][j])
{
a[i][j]=a[i][k]+a[k][j];
}
scanf("%d",&p);
while(p--)
{
scanf("%d%d",&x,&y);
printf("%d\n",ans(x,y)+2);

}
return 0;
}

• @ 2018-05-25 23:27:31
``````#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int edge[101][101];
int n,m,a,b,sum;
int find(int x,int y)
{
sum = 0;
for(int i = 1; i<=n; i++)
if(edge[x][i]+edge[i][y] == edge[x][y]) sum++;
return sum;
}
int main()
{
memset(edge,27,sizeof(edge));
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
cin>>a>>b;
edge[a][b] = 1;
edge[b][a] = 1;

}

for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(edge[i][j]>edge[i][k]+edge[k][j])
edge[i][j]=edge[i][k]+edge[k][j];
int q;
cin>>q;
for(int i = 1; i<=q; i++)
{

cin>>a>>b;
cout<<find(a,b)+2<<endl;
}

return 0;
}
``````

退役快一年了...

竟然WA了半天
忘记换行了...

• @ 2017-11-05 21:05:42

粗糙Floyd
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,p;
int g[108][108],f[108][108];
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&j!=k&&i!=k)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
int seach(int a,int b)
{
int ans=2;
for(int i=1;i<=n;i++)
{
if(i!=a&&i!=b&&g[a][i]+g[i][b]==g[a][b])
ans++;
}
return ans;
}
int main()
{
memset(g,0x7fffffff,sizeof(g));
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j) g[i][j]=0x3f3f3f3f;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
g[x][y]=g[y][x]=1;
}
floyd();
cin>>p;
for(int i=1;i<=p;i++)
{
int a,b;
cin>>a>>b;
cout<<seach(a,b)<<endl;
}
return 0;
}

• @ 2017-11-04 20:27:42

简单的Floyed (≖ ‿ ≖)✧

``````#include<iostream>
#include<cstring>
#define INF 1000000
using namespace std;
int main()
{
int f[105][105];
int n,m,a,b,p,num;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(i==j)
f[i][j]=0;
else
f[i][j]=INF;
}
}
for(int i=1;i<=m;++i)
{
cin>>a>>b;
f[a][b]=f[b][a]=1;
}
for(int k=1;k<=n;k++)
{
for (int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(f[i][k]+f[k][j]<f[i][j]&&i!=j&&i!=k&&j!=k)
{
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
}
cin>>p;
for(int i=1;i<=p;++i)
{
num=0;
cin>>a>>b;
for(int j=1;j<=n;++j)
{
if(f[a][b]==f[a][j]+f[j][b])
num++;
}
cout<<num<<endl;
}
return 0;
}
``````
• @ 2017-10-20 19:05:13

floyd 两遍

``````#include<stdio.h>
#include<string.h>
int n,m;
int map[102][102];
int ans[102][102];
int main()
{
memset(map,0x3f,sizeof(map));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
map[x][y]=1;
map[y][x]=1;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(map[i][k]+map[k][j]<map[i][j])
{
map[i][j]=map[i][k]+map[k][j];
}
}
}
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(map[i][k]+map[k][j]==map[i][j])
{
ans[i][j]++;
}
}
}
}
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",2+ans[x][y]);
}
return 0;
}

``````
• @ 2017-06-08 23:16:27

貌似就我一个傻傻地用了bitset记录最短路点集⊙﹏⊙b
http://www.cnblogs.com/Onlynagesha/p/6965262.html

• @ 2012-09-10 23:57:11

水题面板编 连着WA四次。。。。

• @ 2010-03-08 22:12:43

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

#include

using namespace std;

const int MAXN=10000000;

const int N=101;

int n,m,p;

int f[N][N];

int main(void)

{

int x,y;

cin>>n>>m;

for (int i=1;i>y;

f[x][y]=f[y][x]=1;

}

cin>>p;

for (int k=1;k>y;

for (int k=1;k

• @ 2009-11-04 22:45:16

我还当就输出一条路上的总点数.就判定是样例错了..,.. 写了个Floyd就交了..全部wa

可是是输出最短路上的总点数!!!多条最短路就得用中间点法求点的个数了!!!!!

• @ 2009-10-27 23:57:38

如果 map[a,b]=map[a,k]+map[k,b]

那么 k 就是 a b 最短路上的点。

• @ 2009-10-26 17:15:41

の。看错题了。

• @ 2009-10-25 22:07:29

没什么好说的。。直接floyd。。

输出的时候统计路上节点即可。。

对于wa点的同志们。。小小的提个醒。。floyd枚举的顺序是

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do ...

• @ 2009-10-24 18:44:22

var

bb:array[1..100]of boolean;

f:array[1..100,1..100]of integer;

path:array[1..100,1..100,0..100]of integer;

i,j,k,m,n,p,a,b,ans,t:integer;

procedure print(a,b:integer);

var

i:integer;

begin

if bb then

begin

inc(ans);

bb:=false;

end;

if a=b then exit;

for i:=1 to path[a,b,0] do

print(a,path[a,b,i]);

end;

begin

fillchar(f,sizeof(f),127);

fillchar(path,sizeof(path),0);

for i:=1 to m do

begin

f[a,b]:=1;f:=1;

inc(path[a,b,0]);inc(path);

path[a,b,1]:=a;path:=b;

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (f+f[k,j])

• @ 2009-10-17 21:27:15

学了半年Floyd还真没白学

n=100不用Floyd做还真是天理不容

就是注意一点 .. 答案要+2 (加上起点和终点两个点)

program ex;var a:array[1..100,1..100] of longint ; n,m,p,i,j,x,y,ans:longint ;procedure floyd ;var i,j,k:longint ;begin for k := 1 to n do for i := 1 to n do for j := 1 to n do if (i j) and (j k) and (i k) then if a > a + a[k,j] then begin a := a + a[k,j] ; a[j,i] := a ; end ;end ;BEGIN read(n,m) ; for i := 1 to n do for j := 1 to n do a := maxint ; for i := 1 to m do begin read(x,y) ; a[x,y] := 1 ; a[y,x] := 1 ; end ; floyd ; read(p) ; for i := 1 to p do begin read(x,y) ; ans := 0 ; for j := 1 to n do if a[x,j] + a[j,y] = a[x,y] then inc(ans) ; writeln(ans + 2) ; end ;END .

• @ 2009-09-10 17:27:19

数据太弱了......

• @ 2009-09-05 22:01:46

floyd

ID
1446

5

3512

1329

38%

10