给出一张包含 $n$ 个节点、 $m$ 条边的无向图，现在你可以任意取仅一条边，将它的边权变为原来的 $1/2$，请你求出此时图上两点 $s,t$ 间可能的最短路径长度。

其中 $1 \le n \le 500, 1 \le m \le 50000, 1 \le 边权 \le 500000$ ，保证所有边权为偶数。

我的代码：

#include <bits/stdc++.h>
using namespace std;

int N, M, S, T, u, v, d[514], G[1919][810], w;
bool vis[1919] = {};

void Dijkstra() {
	vis[S] = true;
	for (int i = 1; i <= N; i ++) d[i] = 1145140000;
	d[S] = 0;
	for (int i = 1; i < N; i ++) {
		int n = 0, m = 1145140000;
		for (int j = 1; j <= N; j ++)
			if (!vis[j] && d[j] < m) n = j, m = d[j];
		
		vis[n] = true;
		
		for (int j = 1; j <= N; j ++)
			if (!vis[j] && m + G[n][j] < d[j])
				d[j] = m + G[n][j];
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	
	int mu, mv, mw = -114514;
	cin >> N >> M;
	for (int i = 1; i <= M; i ++) {
		cin >> u >> v >> w;
		G[u][v] = w;
		if (mw < w) mu = u, mv = v, mw = w;
	}
	G[mu][mv] /= 2, G[mv][mu] /= 2;
	cin >> S >> T;
	
	Dijkstra();
	cout << d[T];
	
	return 0;
}