模拟赛题讲解[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：

3 2 5
1 2 3
2 3 3
2
3 2
1 3

输出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;
}