[ABC143] E.Travel by Car

发表于 | 更新于
本文字数： 6.8k

链接

\(\text{ABC143 E - Travel by Car}\)

题意

  给你一个由\(n\)个城镇（编号\(1\)到\(n\)）和\(m\)条路组成的无向图，第\(i\)条路的距离为\(C_i\)； 你将要乘车去一些城镇旅游，你的汽车的油箱的容量是\(L\)，在路上行驶\(1\)单位的距离将消耗\(1\)单位的油，在你旅游途中的每个城镇，你都可以选择加油与不加油，选择加油，你可以将你油箱加满油；现在将对你进行\(Q\)次询问，每次询问从城镇\(S_i\)到城镇\(T_i\)，旅途中的最少加油次数，如果不能抵达输出\(-1\)；

  数据范围：\(2\leq n\leq 300,0\leq M\leq \frac{n(n-1)}{2},1\leq L\leq 10^{9}，S_i\neq T_i,1\leq C_i\leq 10^{9},1\leq Q\leq N(N-1)\).

分析

  这里的查询最多可以有\(N(N-1)\)个，所以我们考虑预处理出任意两点之间的答案；

  首先可以寻找出所有的起始终止城镇\((s_i,t_i)\)，使得从\(s_i\)到\(t_i\)加一次油即可到达，可以通过计算任意两点之间的最短路得出，然后我们在此基础上处理，若两个 城镇之间距离\(\leq L\)，那么它们之间仅加一次油即可，所以将该条边权值赋为\(1\)，若\(>L\)则赋值为\(\infty\)，由此计算任意两城镇之间最短路，此时的最短路，即是最少加油次数；

  对于任意\((s_i,t_i)\)，我们都贪心的考虑，将路径分割成若干段，每一段距离都\(\leq L\)，我们希望得到尽量少的段，所以我们预处理了任意两城市之间的最短路；

  注意开始油箱是满的；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

int n, m, l, q, cost[304][305];

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
}

int main(){
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> m >> l;
    int a, b, c;
    clr(cost, inf);
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        cost[a][b] = cost[b][a] = c;
    }
    floyd();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cost[i][j] = (cost[i][j] <= l ? 1 : inf);
    floyd();
    cin >> q;
    while (q--) {
        cin >> a >> b;
        cout << (cost[a][b] == inf ? -1 : cost[a][b] - 1) << endl;
    }
}