题解：P11795 [JOI 2016 Final] 铁路票价 / Train Fare

ldyldy · 2025-04-06 21:32:37 · 题解

一个基于离线特性而比较容易理解的题解

有一个特性：

把一条边边权增大，之后包含它的路径一定比原最短路权值大。

也就意味着加权值的操作效益等同于删边。

再看到输入的离线特性，就容易想到将边加一个第二权值，定义为 此边何时被删去。

定义一条 1 到 i 点的最短路被破坏，即为无论如何 1 到 i 点的路径无法小于等于原最短路的长度。

因为所有边长度为 1 ，故我们可以使用 BFS 来求单源最短路，顺便求 1 到 i 点的最短路被破坏的时间。

需要注意的是，此处 BFS 来求单源最短路时要考虑到最短路路径相等时也要更新答案。

最后把时间计数排序一下，再用前缀和算一下此时已有多少路径被破坏，然后按 q 输出。

本题，完。

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int u,v,lo;
    bool operator <(const edge &a)const
    {
        return lo>a.lo;
    }
}ed[1000005];
vector <edge>a[100005];
int n,m,q,dis[1000005],dis2[1000005],tpx[1000005],sum[1000005];
void bfs()
{
    for(int i=1;i<=1000000;i++) dis[i]=99999999;
    dis2[1]=99999999;
    dis[1]=0;
    queue<int> q;
    q.push(1);
    long long flag=1;
    while(q.size())
    {
        int now=q.front();
        q.pop();
        for(int i=0;i<a[now].size();i++)
        {
            if(flag)
            {
                if(dis[a[now][i].v]>dis[now]+1)
                {
                    q.push(a[now][i].v);
                    dis[a[now][i].v]=dis[now]+1;
                    dis2[a[now][i].v]=min(dis2[now],a[now][i].lo);
                }
                if(dis[a[now][i].v]==dis[now]+1)
                {
                    dis2[a[now][i].v]=max(dis2[a[now][i].v],min(dis2[now],a[now][i].lo));
                }

            }
        }
    }
}
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        cin>>ed[i].u>>ed[i].v;
        ed[i].lo=99999999;
    }
    for(int i=1;i<=q;i++)
    {
        int x;
        cin>>x;
        ed[x].lo=i;
    }
    for(int i=1;i<=m;i++)
    {
        a[ed[i].u].push_back(ed[i]);
        a[ed[i].v].push_back({ed[i].v,ed[i].u,ed[i].lo});
    }
    bfs();
    for(int i=1;i<=n;i++)
    {
        if(dis2[i]<1000000)tpx[dis2[i]]++;
    }
    for(int i=1;i<=q;i++)
    {
        sum[i]=sum[i-1]+tpx[i];
        cout<<sum[i]<<endl;
    }
    return 0;
}