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

· · 题解

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

是不是有点抄 这道 了（确实是 J 组）？

解题思路

显然一个已经到达的点灯人可以在两座城市之间反复横跳，因此跑出每个点的奇偶最短路就可以了，跑一遍 dijkstra 就可以了。

最后分别求出点中奇偶分别最远的点，如果都有跑不到的点就是无解，否则输出其中的更小一个值即可。

我们自信提交，就可以拿到 24 分 的好成绩，观察大样例二发现我们漏了一条重要信息：“特别地，如果这样的道路不存在，则这位点灯人会失望地离开这个国家”。这样的条件显然只会在 1 号点第 1 秒发生，不然就可以从哪来回哪去，只要再特判一下存不存在 w 为 1 且连接 1 号节点的边就行了。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N=2.5e4+50;
const int inf=1e9+7+2*N;
int c,T;
int n,m,o;
vector<pair<int,int>> G[N];
int dis[N][2];
int vis[N][2];
inline void dijkstra(){
    for(int i=1;i<=n;i++) dis[i][0]=dis[i][1]=inf,vis[i][0]=vis[i][1]=0;
    dis[1][0]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,1});
    while(pq.size()){
        int p=pq.top().second;
        int d=pq.top().first;
        pq.pop();
        if(vis[p][d%2]) continue;
        vis[p][d%2]=1;
        for(auto j:G[p]){
            int u=j.first,w=j.second;
            if(max(dis[p][0]+1,w/2*2+1)<dis[u][1]){
                dis[u][1]=max(dis[p][0]+1,w/2*2+1);
                pq.push({dis[u][1],u});
            }
            if(max(dis[p][1]+1,(w+1)/2*2)<dis[u][0]){
                dis[u][0]=max(dis[p][1]+1,(w+1)/2*2);
                pq.push({dis[u][0],u});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>c>>T;
    while(T--){
        cin>>n>>m>>o;
        for(int i=1;i<=n;i++) G[i].clear();
        bool flag=1;
        for(int i=1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            G[u].push_back({v,w});
            G[v].push_back({u,w});
            if((u==1 || v==1) && w==1) flag=0;
        }
        if(flag){//特判
            cout<<"-1\n";
            continue;
        }
        dijkstra();
        int ans1=0,ans2=0;
        for(int i=1;i<=n;i++){
            ans1=max(ans1,dis[i][0]);
            ans2=max(ans2,dis[i][1]);
        }
        if(ans1>=inf && ans2>=inf) cout<<"-1\n";
        else cout<<min(ans1,ans2)*o<<'\n';
    }
}