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

#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;
}