最短路【Floyd算法模板】

userId_undefined

谁来教我C++

荣耀黄金

2023-08-19 16:04:40

发布于：浙江

82阅读
0回复
0点赞
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e4+5;
const ll INF = 1e9;

int s[N][N];
int n,m,q; 

int main(){

	cin >> n >> m;
	//初始化 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i != j)	s[i][j] = INF;
			else 	s[i][j] = 0;
		}
	}
	//存图 
	for(int i=1;i<=m;i++){
		int u,v,w;//起点、终点、距离 
		cin >> u >> v >> w;
		s[u][v] = min(s[u][v],w); 	//单向存图
//		s[v][u] = min(s[v][u],w);	//双向存图 
	} 
	//最短路 
	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];
				}
			}
		}
	}
	cin >> q;//q次查询 
	while(q--){
		int x,y;//输入需要查询的起点位置和终点位置 
		cin >> x >> y;
		cout << s[x][y]<<endl;
	}
	
	
	return 0;
}
userId_undefined
去预览
0/2000

全部评论 42

热门讨论