24 Pts 求调

#include <bits/stdc++.h>
#define int long long
#define N 25005
#define INF 1e18
using namespace std;

int c,t;
int n,m,o;
struct Edge{
	int v,w;
};
vector<Edge> g[N];
int vis[N][2];

struct Node{
	int u,ans;
};


void bfs(){
	queue<Node> q;
	q.push({1,0});
	vis[1][1] = 0;
	
	while (q.size()){
		int u = q.front().u;
		int ans = q.front().ans;
		q.pop();
		if (vis[u][ans%2] <= ans) continue;
		vis[u][ans%2] = ans;
		
		for (auto [v,w] : g[u]){
			if (ans + 1 < w) ans += ceil(1.0*(w-ans-1)/2.0)*2;
			q.push({v,ans+1});
		}
	}
}

signed 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){
			vis[i][0] = INF;
			vis[i][1] = INF-1;
		}
		for (int i=1;i<=n;++i) g[i].clear();
		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});
		}
		
		bool is = true;
		for (auto [v,w] : g[1]){
			if (w <= 1) is = false; 
		}
		if (is){
			cout << "-1\n";
			continue;
		}
		
		bfs();
		int ans1 = -1,ans2 = -1;
		bool is_ou=false,is_ji=false;
		for (int i=1;i<=n;++i){
			if (vis[i][0] == INF) is_ou = true;
			if (vis[i][1] == INF) is_ji = true;
		}
		if (is_ou && is_ji){
			cout << -1 << '\n';
			continue;
		}
		for (int i=1;i<=n;++i) ans1 = max(ans1,vis[i][0]);
		for (int i=1;i<=n;++i) ans2 = max(ans2,vis[i][1]);
		//cout << vis[7] << ' ';
		int ans = INF;
		if (!is_ou) ans = min(ans,ans1);
		if (!is_ji) ans = min(ans,ans2);
		cout << ans * o << '\n';
	}
	
	
	
	
	return 0;
}