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