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

· · 题解

一些闲话

各位大佬的做法都好神秘啊（应该是我太蒟蒻看不懂）。\ 五十分钟场切的，用的是深搜叠记忆化。\ 膜拜神犇 Hootime 和 TA 的 npy chenyuexiC2026。

题意转化

赛时看到这道题感觉长得很像 加工零件，所以往这方面想了一下。\ 由于最开始可以理解为有无限多的人，所以肯定是联通且能走的所有节点全都有无限的人走过去。\ 而在下一天，又有无限的人回到这一个点。\ 具体来说，如果第 i 天能走到 x 节点，那么 i+2 天一定能走到 x 节点，因为只要走到了 x 节点，上一步走过来的那一条边可以支持它拖 2 的时间。\ 然后就很明显跑一个奇偶步数最短路。\ 这个时候 1 节点就会出现问题，因为只有 1 节点没有上一步。\ 但是题目中有这么一句话：特别地，如果这样的道路不存在，则这位点灯人会失望地离开这个国家。\ 那就简单了，如果开始时 1 节点没有任何一个点可以移动，答案就是 -1。

具体做法

由于我并不会 Dijkstra 的一些神秘形式，于是打了一个记忆化。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b) 
int C,T,n,m,o,head[100005],next1[200005],to[200005],zhi[200005],cnt,aa,bb,cc,minn = 1,m1,m2,l = 1,r = 1,que[8000005][2];
#define add(a,b,c) (++cnt,to[cnt] = b,zhi[cnt] = c,next1[cnt] = head[a],head[a] = cnt)
int dist[100005][2];
void sou(){
//由于调大样例的时候递归爆炸了，于是写了一个队列，但实质上还是 DFS
    que[1][0] = 1,que[1][1] = 0;
    while(l <= r){
        int x = que[l][0],num = que[l][1];
        int qfr = num & 1;
        ++l;
        for(int i = head[x];i;i = next1[i]){
            int y = to[i];
            if(num >= zhi[i]){
                int xp = (num+1) & 1;
                if(num+1 >= dist[y][xp]) continue;
                dist[y][xp] = num+1;
                ++r;
                que[r][0] = y,que[r][1] = num+1;
            }
            else{
                int yqyq = (zhi[i] + 1 + ((zhi[i] - num) & 1));
                int xp = yqyq & 1;
                if(yqyq >= dist[y][xp]) continue;
                dist[y][xp] = yqyq;
                ++r;
                que[r][0] = y,que[r][1] = yqyq;
            }
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> C >> T;
    while(T--){
        cin >> n >> m >> o;
        for(int i = 1;i <= cnt;++i) next1[i] = to[i] = zhi[i] = 0;
        for(int i = 1;i <= n;++i) head[i] = 0,dist[i][0] = dist[i][1] = 1e16;
        cnt = 0,minn = 1e16,m1 = 0,m2 = 0,l = 1,r = 1;
        for(int i = 1;i <= m;++i){
            cin >> aa >> bb >> cc;
            --cc;//方便搜索
            add(aa,bb,cc),add(bb,aa,cc);
        }
        for(int i = head[1];i;i = next1[i]) minn = min(minn,zhi[i]);
        if(minn != 0){
            cout << -1 << endl;
            continue;
        }
        sou();
        for(int i = 1;i <= n;++i) m1 = max(m1,dist[i][0]);
        for(int i = 1;i <= n;++i) m2 = max(m2,dist[i][1]);
        int ansss = min(m1,m2);
        if(ansss >= (int)1e14) cout << -1 << endl;
        else cout << ansss * o << endl; 
    }
    return 0;
}