时间复杂度是O(n^2)

#include<bits/stdc++.h>
using namespace std;
int n,m,q;//q次查询 
int start,end,value;
bool vis[7501];
int w[7501][7501];//按照正常的六千四百万向下开
inline void Floyd(int s){
	for(int k=1;k<=n;k++){
		for(int j=1;j<=n;j++)w[s][j]=min(w[s][j],w[s][k]+w[k][j]);
	}
} 
int main(){
	cin>>n>>m>>q;
	memset(w,0x3f,sizeof(w));
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&start,&end,&value);
		w[start][end]=w[end][start]=value;
	}
	for(int i=1;i<=q;i++){
		scanf("%d%d",&start,&end);
		if(!vis[start])Floyd(start);
		vis[start]=1;
		printf("%d\n",w[start][end]);
	}
	return 0;
}