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

anke2017 · 2025-10-25 18:10:51 · 题解

一眼看上去有些难。

如果第一个城市的所有道路第 1 天不开放，则答案显然为 -1。

然后，我们发现：如果一个城市上第 d 天有人，那么第 d+2 天也有人（肯定有人随便找一条边走一天，然后再走回来）。

于是，我们令 f_{i,0/1} 表示模 2 余 0/1 的天数中，最快什么时候有人。因为在这之后，肯定也有人。

转移可以用形如 dijkstra 的方法。初始时 f_{1,0}=0。

所以，我们要求的就是

时间复杂度 O(m\log{m})。

当然，这个建模可以稍微进行一些拓展。如果题目存在（一些诡异的条件）说 k 步后可以回来，复杂度就是 O(mk\log{mk})。

代码：

#include<bits/stdc++.h>

using namespace std;
//#define int long long
int dij[30010][2];
struct edge{
    int to,v;
};
vector<edge> e[30010];
struct node{
    int now,type,v;
    bool operator <(const node tmp)const
    {
        return v>tmp.v;
    }
};
void dijk()
{
    priority_queue<node> q;
    memset(dij,0x3f,sizeof(dij));dij[1][0]=0;
    q.push((node){1,0,0});
    while(q.size())
    {
        auto t=q.top();q.pop();
        if(dij[t.now][t.type]<t.v)continue;
        for(auto x:e[t.now])
        {
            int to=max(x.v,t.v+1);
            if(x.v>t.v+1&&x.v%2!=(t.v+1)%2)to++;
            if(dij[x.to][to&1]>to)
            {
                dij[x.to][to&1]=to;
                q.push((node){x.to,to&1,to});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int c,t;cin>>c>>t;
    while(t--)
    {
        int n,m,k;cin>>n>>m>>k;
        for(int i=1;i<=n;i++)
            e[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v,w;cin>>u>>v>>w;
            e[u].push_back((edge){v,w});
            e[v].push_back((edge){u,w});
        }
        bool f=1;
        for(auto x:e[1])
        {
            if(x.v==1)f=0;
        }
        if(f)
        {
            cout<<"-1\n";
            continue;
        }
        dijk();
//      for(int i=1;i<=n;i++)
//          cout<<dij[i][0]<<' ';
//      cout<<'\n';
//      for(int i=1;i<=n;i++)
//          cout<<dij[i][1]<<' ';
//      cout<<'\n';
        int ans=0x3f3f3f3f;
        for(int x=0;x<2;x++)
        {
            int now=0;
            for(int i=1;i<=n;i++)
                now=max(now,dij[i][x]);
            ans=min(ans,now);
        }
        if(ans==0x3f3f3f3f)cout<<"-1\n";
        else cout<<ans*k<<'\n';
    }
    return 0;
}