• 题面描述

N 个点， M 条边单向边。

Q 个问题，每次询问 u， v 两点间最短路与最短路方案数。 如果两个点之间不存在最短路则输出-1

• 输入

第一行三个整数：N， M， Q 接下来 M 行，每行三个整数：u, v, w 表示 u 到 v 有一个长度为 w 的边 接下来 Q 行，每行两个整数 u, v， 表示查询的点对。

u， v 两点间最短路与最短路方案数， 用空格隔开 如果两个点之间不存在最短路则输出-1

• 输入样例

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

• 输出样例

5 1
-1

数据范围 $1≤n≤500$

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std; 
#define INF 0x3f3f3f3f
int n,m,u,v,w,q;
int dis[3000][3000];
int cnt[3000][3000];
signed main(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=INF;
			dis[i][i]=0;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		dis[u][v]=min(dis[u][v],w);
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dis[i][k]!=INF&&dis[k][j]!=INF){
					dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
				}                     
			}
		}
	}
	int minn=-114514;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			minn=min(minn,dis[i][j]);
			int xx=i,yy=j;
			++cnt[xx][yy];
		}
	}
	for(int i=1;i<=q;i++){
		int qx,qy;
		cin>>qx>>qy;
		if(dis[qx][qy]!=INF){   
			cout<<dis[qx][qy]<<" "<<cnt[qx][qy]<<endl; 
		}
		else cout<<"-1"<<endl; 
	}
	return 0;
}

想问最短路数量到底该怎么求？玄关