最短路【Floyd算法模板】
2023-08-19 16:04:40
发布于：浙江
93阅读
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;
}
全部评论 42
̴̵̶̷̸̡̢̧̨̛̖̗̘̙̜̝̞̟̠̣̤̥̦̩̪̫̬̭̮̯̰̱̲̳̹̺̻̼͇͈͉͍͎̐̑̒̓̔̽̾̿̀́͂̓̈́͆͊͋͌̕̚ͅ͏͓͔͕͖͙͚͐͑͒͗͛ͣ͘͜͟͢͝͞͠͡
2024-02-02 来自 北京
0
̴̵̶̷̸̡̢̧̨̛̖̗̘̙̜̝̞̟̠̣̤̥̦̩̪̫̬̭̮̯̰̱̲̳̹̺̻̼͇͈͉͍͎̐̑̒̓̔̽̾̿̀́͂̓̈́͆͊͋͌̕̚ͅ͏͓͔͕͖͙͚͐͑͒͗͛ͣͤͥͦͧͨͩͪͫͬͭͮͯ̀́̂̃̄̅̆̇̈̉̊̋̌̍̎̏̐̑̒͘͜͟͢͝͞͠͡ ̴̵̶̷̸̡̢̧̨̛̖̗̘̙̜̝̞̟̠̣̤̥̦̩̪̫̬̭̮̯̰̱̲̳̹̺̻̼͇͈͉͍͎̐̑̒̓̔̽̾̿̀́͂̓̈́͆͊͋͌̕̚ͅ͏͓͔͕͖͙͚͐͑͒͗͛ͣ͘͜͟͢͝͞͠͡
2023-08-19 来自 浙江
0
有帮助，赞一个