模拟赛题讲解[25]

来自 s_r_f 2023-08-02 noi.ac #3193

题目描述：

小 C 生活在一个城市里。这个城市里有 $n$ 个点 $1,2,\cdots n$ 和 $k$ 条地铁线路，每条地铁线路用 $(l,a,b,c)$ 表示，包含 $(l,l+a,l+2a,l+3a…,l+ab)$ ，保证 $1 \leq l < l + ab \leq n$，$a,b \geq 1,c \geq 0$. 可以从地铁线路中的任何一站以 $c$ 的费用到达线路中的任何其它站。

还有 $n-1$ 条道路，连接点 $i$ 和 $i+1$，费用为 $v_i$。所有的道路都是双向的。

因为城市建设的某些原因，不存在两个 $a$ 相等的地铁线路。

小 C 想知道，从 $1$ 出发，只通过给出的道路和线路，到 $2,3,\cdots,n$ 的最少费用。

输入格式：

第一行，两个整数 $n$ 和 $k$ ，用空格隔开。

接下来 $k$ 行，每行四个整数 $l,a,b,c$，用空格隔开。

接下来 $1$ 行 $n-1$ 个整数 $v_1 \cdots v_{n-1}$ ，用空格隔开。

输出格式：

输出一行。

一行 $n-1$ 个数 $\mathrm{ans}_2,~\mathrm{ans}_3,~\cdots,~\mathrm{ans}_n$ ，用空格隔开。

样例输入1：

3 1
1 2 1 5
100 5

样例输出1：

10 5

数据范围：

子任务 1(30pts) : $n,k \leq 1000$

子任务 2(30pts) $:$ $c,v_i = 1$

子任务 3(30pts) $:$ $n \leq 20000$

子任务 4(10pts) : $2 \leq n \leq 50000,k \leq n ,0 \leq c,v_i \leq 10^9$

题解：

考虑将进入地铁看作一个点 $P$ ，对于当前地铁点集中的所有点 $x$ ，连边 $(x,P,c)$ 和 $(P,x,0)$ 。

分析下复杂度。注意到 $a$ 两两不同，且每组边最多涉及 $\mathcal{O}(n/a)$ 个点

观察到 $\sum_{i=1}^n\left\lceil\frac{n}{i}\right\rceil$ 在 $n=50000$ 时是 $T=598695$ ，复杂度不超过 $\Theta(T \log T)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e4 + 15))

int n,m,pos=1,head[N << 2],d[N << 2]; bitset<(N << 2)> vis;
struct Edge { int u,v,w,next; } e[N << 6];
void addEdge(int u,int v,int w) { e[++pos] = {u,v,w,head[u]}; head[u] = pos++; }
struct node { int u,dis; };
priority_queue<node> q;
bool operator<(node a,node b) { return a.dis > b.dis;}
void Dijkstra()
{
    memset(d, 0x3f, sizeof(d));
    d[1] = 0; q.push({1, 0});
    while(!q.empty())
    {
        int u = q.top().u; q.pop(); if(vis[u]) continue; vis[u] = 1;
        for(int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;
            if(d[v] > d[u] + e[i].w)
            {
                d[v] = d[u] + e[i].w;
                q.push({v, d[v]});
            }
        }
    }
}
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;
    for(int i = 1, l,a,b,c; i <= m; i++)
    {
        cin >> l >> a >> b >> c;
        for(int j = l; j <= n && j <= l + a * b; j += a) {
            addEdge(j, n + i, 0); addEdge(n + i, j, c);
        }
    }
    for(int i = 1, w; i < n; i++)  {
        cin >> w; addEdge(i, i + 1, w); addEdge(i + 1, i, w);
    }
    Dijkstra();
    for(int i = 2; i <= n; i++) cout << d[i] << " \n"[i == n];
    return 0;
}