NC14697. 最短路径
描述
现在给出一幅有向图（有重边，无自环），问你多少组点对满足他们之间的最短路=d，输出点对的个数。
输入描述
第1行输入三个整数n，m，d，表示图的点数，边数和查询的值。
第2-m+1行，每行输入三个整数s,t,v，表示边的起点，终点和边权。
数据保证：0<n≤50，0<m≤5000，0<d≤5000，0<s,t≤n，0<v≤100。
输出描述
输出一行，一个整数表示满足条件的点对个数。
示例1
输入:
2 2 1 1 2 1 2 1 2
输出:
1
说明:
只有1到2的最短路是1，所以只有1个。示例2
输入:
2 2 1 1 2 1 2 1 1
输出:
2
说明:
1到2和2到1的最短路都是1，所以有2个。C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 392K, 提交时间: 2022-08-12 18:57:02
#include<bits/stdc++.h>
using namespace std;
int e[60][60];
int main()
{
int n,m,d,a,b,c,x=0;
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
e[a][b]=c;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(e[i][j]>e[i][k]+e[k][j])
{
e[i][j]=e[i][k]+e[k][j];
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&e[i][j]==d)
{
x++;
}
}
}
printf("%d\n",x);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 504K, 提交时间: 2020-02-14 22:08:19
#include<stdio.h>
int e[60][60];
int main()
{
int n,m,d,a,b,c,x=0;
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
e[a][b]=c;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&e[i][j]==d) x++;
printf("%d\n",x);
return 0;
}