模拟赛题讲解[4]

来自 Roundgod 2022-07-26 noi.ac #2680

问题描述：

Berland由 $n$ 个城市和 $m$ 条双向道路构成，其中第 $i$ 条道路连接城市 $a_i$ 和 $b_i$ ，并且距离 $c_i$ 公里.

你想要开车在Berland进行自驾游。已知车子的油箱最多能装 $L$ 升油，并且车子每行进一公里都要耗费恰好一升油。当你到达某个城市的时候，你可以选择将油箱加满油(也可以不加)。你不能在道路中间加油。

现在给出 $q$ 组如下形式的询问: 给定起点 $s$ 和终点 $t$ ，问如果初始时油箱装满从城市 $s$ 出发，最少要多少次加满油才能到达城市 $t$ ，如果无法到达输出 $−1$.

输入格式：

输入第一行包含 $3$ 个整数 $n,m,L$分别表示城市的个数，道路的条数以及油箱的容量。

接下来 $m$ 行，每行包含三个整数 $a_i,b_i,c_i(1\le a_i,b_i\le n,a_i\ne b_i)$ ，表示第 $i$ 条道路连接的城市以及道路长度。

接下来一行输出一个整数 $q$ ，表示询问的组数。

接下来 $q$ 行，每行输入两个整数 $s_i,t_i(1\le s_i,t_i\le n,s_i \ne t_i)$ ，表示每组询问。

输出格式

对于每组询问，你需要在一行中输出一个整数表示答案。

输入1：

输出1：

0
1

输入2：

4 0 1
1
2 1

输出2：

-1

数据范围：

对于 $40\%$ 的数据，$1\le n\le 300,~1\le m\le 2000,~1\le L\le 10^9,~1\le q\le n(n−1),~c_i=L$

对于 $100\%$ 的数据，$1\le n\le 300,~1\le m\le \frac{n(n−1)}{2},~1\le L\le 10^9,~1\le q\le n(n−1),~1\le c_i\le 10^9$

题解：

~~关于老师数据挂了，改完我就rank1这件事~~

首先，如果一条路径的边权和小于等于 $L$ ，那我们只要加一次油就可以了

因此我们可以认为在路径上的这些结点两两有花费为 $1$ 的边权（加油次数）

然后两遍 $\text{Floyd}$ 就好了，具体可以看代码

有一说一，虽然思路是这样的，但是我的实现和讲解的不太一样

所以我把标程搬过来了，可以参考一下

~~有没有一种可能，我自己都没看懂自己的写法~~

其实我的实现是 $f_{i,j}$ 表示从 $i$ 出发到 $j$

因为只有一个起点，因此另一个起点加满的油在合并时是要加上的，故

$f_{i,j}=\min\{f_{i,j},~f_{i,k}+f_{k,j}+1\}$

时间复杂度 $O(n^3)$

我的考场代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x7f7f7f7f
#define N (int)(305)

int n,m,L,Q,f[N][N],g[N][N],tmp[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> L;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f[i][j]=g[i][j]=tmp[i][j]=INF;
    for(int i=1,u,v,w; i<=m; i++)
    {
        cin >> u >> v >> w;
        g[u][v]=min(g[u][v],w);
        tmp[u][v]=tmp[v][u]=g[v][u]=g[u][v];
    }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                tmp[i][j]=min(tmp[i][j],tmp[i][k]+tmp[k][j]);
        int ok=0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(tmp[i][j]<=L) g[i][j]=min(g[i][j],tmp[i][j]),ok=1;
        if(!ok) break;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(g[i][j]<=L) f[i][j]=0;
    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]+1);
    cin >> Q;
    for(int x,y; Q--;)
    {
        cin >> x >> y;
        cout << ((f[x][y]==INF)?-1:f[x][y]) << '\n';
    }
    return 0;
}

老师的std：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 305
#define INF 1000000001
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,m,l,q;
int d[MAXN][MAXN];
void floyd_warshall()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&l);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            d[i][j]=(i==j?0:INF);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        d[u][v]=min(d[u][v],w);
        d[v][u]=min(d[v][u],w);
    }
    floyd_warshall();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(d[i][j]>l) d[i][j]=INF; else d[i][j]=(i==j?0:1);
    floyd_warshall();
    scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%d\n",d[u][v]==INF?-1:d[u][v]-1);
    }
    return 0;
}