Description

　　一個無向圖上，沒有自環(huán)，所有邊的權值均為1，對于一個點對（a,b）,我們要把所有a與b之間所有最短路上的點的總個數(shù)輸出。

Input

第一行n,m,表示n個點，m條邊
接下來m行，每行兩個數(shù)a,b,表示a,b之間有條邊
在下來一個數(shù)p,表示問題的個數(shù)
接下來p行，每行兩個數(shù)a,b,表示詢問a,b

Output

對于每個詢問，輸出一個數(shù)c,表示a,b之間最短路上點的總個數(shù)

Sample Input

5 6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4

Sample Output

4
3
2

Hint

范圍：n<=100，p<=5000
.
.
.
.
.

分析

應該預處理a數(shù)組，將權值設為無窮大
然后讀入題目中的p組問題
用循環(huán)類似于floyd那樣過一次就好了（能匹配上的+1）
.
.
.
.
.

程序：

#include <iostream> using namespace std; int a[101][101],n,p,ans,m; int main() {cin>>n>>m;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++) a[i][j]=100000;int x,y;for (int i=1;i<=m;i++){cin>>x>>y;a[x][y]=1;a[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 (a[i][k]+a[k][j]<a[i][j])a[i][j]=a[i][k]+a[k][j];cin>>p;for (int i=1;i<=p;i++){ans=2;cin>>x>>y;for (int l=1;l<=n;l++) if (a[x][l]+a[l][y]==a[x][y]&&x!=l&&l!=y) ans++;cout<<ans<<endl;}return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/9499957.html

總結

以上是生活随笔為你收集整理的最短路上的统计(Floyd)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。