乌拉拉市有n个共享电车桩点和m条双向道路,第 i 条道路连接 a i 和 b i ,长度为 c i 单位距离。计算鸭每次使用一辆共享电车可以行驶 L 单位距离。更换共享电车只能在n个共享电车桩点更换,不能在路上更换,因为路上没有共享电车桩点。 现在计算鸭现在在规划行程,他有 q 个问题想要问你,第 i 个问题是:在s i 点扫码租一辆共享电车后,想要到达t i ,路途中,计算鸭最少需要更换几次共享电车,如果无法到达就是 −1。 输入格式: 第一行输入三个整数 n,m,L,含义如题所示 接下来 m 行,每行输入三个正整数 a i ,b i ,c i ,含义如题所示 然后在一行中输入一个正整数 q,代表询问的次数 最后 q 行,每行输入两个正整数 s i ,t i ,含义如题所示 2≤n≤300 0≤m≤ 2 n×(n−1) 1≤a i ,b i ,s i ,t i ≤n 1≤L,c i ≤10 9 1≤q≤n×(n−1) 输入保证无重边和自环; 询问中 s i =t i 输出格式: 输出共 q 行,第 i 行代表第 i 次询问的结果 输入样例: 3 2 5 1 2 3 2 3 3 2 3 2 1 3 输出样例: 0 1 输入样例: 4 0 1 1 2 1 输出样例: -1c++代码
时间: 2023-12-03 11:43:26 浏览: 88
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310, M = N * N, INF = 1e9;
int n, m, q, L;
int h[N], e[M], ne[M], w[M], idx;
int dist[N][N];
struct Node
{
int p, d;
bool operator< (const Node& t) const
{
return d > t.d;
}
};
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra(int start)
{
priority_queue<Node> heap;
memset(dist[start], 0x3f, sizeof dist[start]);
dist[start][start] = 0;
heap.push({start, 0});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.p, distance = t.d;
if (dist[start][ver] != distance) continue;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[start][j] > distance + w[i])
{
dist[start][j] = distance + w[i];
heap.push({j, dist[start][j]});
}
}
}
}
int main()
{
cin >> n >> m >> L;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
for (int i = 1; i <= n; i ++ ) dijkstra(i);
cin >> q;
while (q -- )
{
int x, y;
cin >> x >> y;
if (dist[x][y] > L) puts("-1");
else
{
int res = INF;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (dist[x][i] + dist[j][y] + dist[i][j] <= L)
res = min(res, dist[x][i] + dist[j][y] + dist[i][j]);
cout << res << endl;
}
}
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)