lanqiao oj 1121 蓝桥公园(floyd)

简介: lanqiao oj 1121 蓝桥公园(floyd)

用户登录

多源求最短路

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
typedef long long LL ;
const LL N = 410 , INF = 0x3f3f3f3f3f3f3f3f;//最大值 
LL f[N][N] ;
LL n , m , q ;
 
int main(){
  cin >> n >> m >> q ;
  for(int i = 1 ; i <= n ;i ++){
    for(int j =1 ; j <= n ; j ++){
      f[i][j] = INF ;
    }
  }
  for(int i = 1 ; i <= m ; i++){
    LL a, b, c ;
    cin >> a >> b >> c ;
    f[a][b] = f[b][a] = min(c,f[a][b]) ;//可能有重边 
  }
  for(int k = 1 ; k <= n ; k++){
    for(int i = 1 ; i <= n ; i ++){
      for(int j = 1 ; j <= n ; j ++){
        f[i][j] = min(f[i][j] , f[i][k] + f[k][j]) ;
      }
    }
  }
  for(int i = 1 ; i <= q ; i ++){
    LL a , b ; cin >> a >> b ;
    if(f[a][b] == INF) cout << "-1" << endl ;//如果没更新过,就说明没有公共边,就输出-1 
    else if(a == b) cout << "0" << endl ;//如果相等就输出0 
    else cout << f[a][b] << endl ;
  }
  return 0 ;
} 
目录
相关文章
|
2月前
lanqiao OJ 1505 剪邮票
lanqiao OJ 1505 剪邮票
27 0
|
2月前
lanqiao OJ 364 跳石头
lanqiao OJ 364 跳石头
34 6
|
2月前
lanqiao oj 1135 蓝桥幼儿园(并查集)
lanqiao oj 1135 蓝桥幼儿园(并查集)
27 0
|
2月前
lanqiao oj 17136 星球(状态压缩dp)
lanqiao oj 17136 星球(状态压缩dp)
12 0
|
2月前
lanqiao OJ 2097 青蛙过河
lanqiao OJ 2097 青蛙过河
11 0
|
2月前
|
BI
lanqiao OJ 蜗牛
lanqiao OJ 蜗牛
19 0
|
2月前
lanqiao oj 1122 蓝桥王国
lanqiao oj 1122 蓝桥王国
17 0
|
2月前
lanqiao oj 186 糖果(状态压缩dp)
lanqiao oj 186 糖果(状态压缩dp)
15 0
|
2月前
lanqiao OJ 102 青蛙跳杯子
lanqiao OJ 102 青蛙跳杯子
26 0
|
2月前
lanqiao OJ 234 大胖子走迷宫
lanqiao OJ 234 大胖子走迷宫
11 0