icontofig | 发布于 2019-07-02 22:54:54 | 阅读量 114 | 最短路

## 题解

n<=1000,还是稠密图，Floyd稳稳的……

`mp[i][j] = min(mp[i][j],mp[i][k] + mp[k][j]);﻿`

## 代码

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
int t[maxn];
int mp[maxn][maxn];
int ans = 0;
int n,m,q;
int cur = -1;
const int INF = 1e9;
void update(int k){
for(int i = 0;i < n;++i)
for(int j = 0;j < n;++j)
mp[i][j] = min(mp[i][j],mp[i][k] + mp[k][j]);
return;
}
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<1) + (num << 3) + c - '0';
return (flag ? -1 : 1) * num;
}
int x,y,z;
int main(){
n = get_num();
m = get_num();
for(int i = 0;i < n;++i){
t[i] = get_num();
}
for(int i = 0;i < n;++i){
for(int j = 0;j < i;++j)
mp[i][j] = mp[j][i] = INF;
}
for(int i = 1;i <= m;++i){
x = get_num();
y = get_num();
z = get_num();
mp[x][y] = mp[y][x] = z;
}
q = get_num();
for(int i = 1;i <= q;++i){
x = get_num();
y = get_num();
z = get_num();
while(t[cur+1] <= z && cur+1 < n){
cur++;
update(cur);
}
if(t[x] > z || t[y] > z || mp[x][y] == INF)printf("-1\n");
else printf("%d\n",mp[x][y]);
}
return 0;
}```

114 人读过

0 条评论