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

BennyT · 2025-10-27 12:54:47 · 题解

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

思路

首先如果再时刻 t 到达了某个点，则后面 t+2k 时刻都能到达这个点，因为可以再两个点之间来回走。

接下来跑奇偶最短路就行了，然后判断是否所有点都能在奇或偶时刻到达即可。

最后记得当 o=0 时无解仍需输出 -1。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN=25010;
int t,n,m,o;
struct N{
    ll y,v;
    bool operator<(const N &n1)const{
        return v>n1.v;
    }
};
vector<N> e[NN];
ll dis[NN][2];
bool vis[NN][2];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t>>t;
    while(t--){
        memset(e,0,sizeof(e));
        cin>>n>>m>>o;
        for(int i=1,x,y,v;i<=m;i++){
            cin>>x>>y>>v;
            e[x].push_back({y,v});
            e[y].push_back({x,v});
        }
        ll mn=1e9;
        for(N i:e[1])mn=min(mn,i.v);
        if(mn>1){
            cout<<"-1\n";
            continue;
        }
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        priority_queue<N> q;
        q.push({1,0});
        dis[1][0]=0;
        while(!q.empty()){
            N t=q.top();
            q.pop();
            if(vis[t.y][t.v%2])continue;
            vis[t.y][t.v%2]=1;
            for(N i:e[t.y]){
                ll tt;
                if(i.v<=t.v+1)tt=t.v+1;
                else{
                    tt=i.v;
                    if(tt%2==t.v%2)tt++;
                }
                if(dis[i.y][tt%2]>tt){
                    dis[i.y][tt%2]=tt;
                    q.push({i.y,tt});
                }
            }
        }
        ll ans=1e18;
        for(int j=0;j<2;j++){
            ll mx=0;
            for(int i=1;i<=n;i++){
                if(dis[i][j]>mx)mx=dis[i][j];
            }
            if(mx!=0x3f3f3f3f3f3f3f3f)ans=min(ans,mx);
        }
        if(ans==1e18)cout<<"-1\n";
        else cout<<ans*o<<'\n';
    }
    return 0;
}