题解：P14307 【MX-J27-T4】点灯

· · 题解

题目传送门

题目大意

给出一张无向图，每条边有一个可通行时刻，第 0 时刻点亮 1 号点，下一时刻熄灭所有的灯，并点亮所有与原来点亮的点直接相连且通行的点，求一个最小时间 d ，满足 d 时刻可以点亮所有的点。

解题思路

首先很容易想到，点灯人可以在两个直接相连且通行的点间反复横跳，直到下一条边可通行。

那么当到达一个点 u 时时间为 t ，可以证明 t + 2 \cdot k 时刻也可以到达这个点，说明当两个点 u 和 v 的 t_u 和 t_v 的奇偶性相同，那么它们可以满足在同一时刻到达，且最小时间为 \max(t_u,t_v) 。

所以对于每个点维护到达它们的最小奇数时刻和偶数时刻，只要满足所有点都能奇数时刻到达或偶数时刻到达，就有解，且 d 为满足条件的时刻中的较小值。

那如何从一个点跳到另一个点？设上一个点到达时间为 t ,边的通行时间为 w 。

可以发现这是一个最短路问题，可用 Dijkstra 算法来维护这一过程。

Code

#include<bits/stdc++.h>
using namespace std;
int c,t,n,m,o,u,v,w,tim1[25005],tim2[25005];//tim1和tim2分别维护 奇数和偶数两种情况
vector<pair<int,int> >q[25005];//邻接表存图 
struct aaa
{
    int to,s;//to是这次到的点，s为对应时间 
};
bool operator<(aaa x,aaa y)
{
    return x.s>y.s;
}
priority_queue<aaa>p;
int main()
{
    cin>>c>>t;
    while(t--)
    {
        cin>>n>>m>>o;
        for(int i=1;i<=n;i++)
        {
            q[i].clear();
            tim1[i]=2e9;
            tim2[i]=2e9;
        }
        //多测不清空见祖宗
        for(int i=1;i<=m;i++)
        {
            cin>>u>>v>>w;
            q[u].push_back(make_pair(v,w));
            q[v].push_back(make_pair(u,w));
        }
        int fg=0;
        for(int i=0;i<q[1].size();i++)
        {
            if(q[1][i].second==1) fg=1;
        }
        if(!fg)
        {
            cout<<"-1\n";
            continue;
        }
        //这里特判从1号点不能在1时刻向外扩散的情况（不然你上哪横跳去）
        tim2[1]=0;
        p.push((aaa){1,0});
        while(!p.empty())
        {
            int k=p.top().to,h=p.top().s;
            p.pop();
            for(int i=0;i<q[k].size();i++)
            {
                int x=q[k][i].first,y=q[k][i].second,d=0;
                if(y<=h+1) d=h+1;
                else
                {
                    if(h%2!=y%2) d=y;
                    else d=y+1;
                }
                //d为最小时间，思路看上面
                if(d%2)
                {
                    if(tim1[x]>d)
                    {
                        tim1[x]=d;
                        p.push((aaa){x,d});
                    }
                }
                else
                {
                    if(tim2[x]>d)
                    {
                        tim2[x]=d;
                        p.push((aaa){x,d});
                    }
                }
                //分成奇数和偶数进行讨论
            }
        }
        int ans1=0,ans2=0;
        for(int i=1;i<=n;i++) ans1=max(ans1,tim1[i]);
        for(int i=1;i<=n;i++) ans2=max(ans2,tim2[i]);
        //统计最大值，因这时才能到达所有点 
        if(ans1==2e9&&ans2==2e9) cout<<"-1\n";//两种情况都不行 
        else cout<<min(ans1,ans2)*o<<"\n";
    }
    return 0;
}