1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10000 + 5;
const int MAXM = 40000 + 5;
const ll INF = 1e15;
struct Edge {
int v, nxt;
ll w;
} edge[MAXM << 1];
struct Edge2 {
int v, nxt;
} edge2[MAXN << 1];
int head[MAXN], head2[MAXN], cnt, cnt2;
inline void AddEdge(int u, int v, ll w) {
edge[++cnt].v = v;
edge[cnt].w = w;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
inline void AddEdge2(int u, int v) {
edge2[++cnt2].v = v;
edge2[cnt2].nxt = head2[u];
head2[u] = cnt2;
}
int t, n, m;
ll d[MAXN];
int fa[MAXN];
bool vis[MAXN];
void Dijkstra(int s) {
for (int i = 1; i <= n; ++i) {
d[i] = INF;
vis[i] = 0;
}
d[s] = 0;
priority_queue<pair<ll, int> > q;
q.push(make_pair(0, s));
while (q.size()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].v;
ll w = edge[i].w;
if (d[v] == INF || d[u] + w < d[v]) {
fa[v] = u;
d[v] = d[u] + w;
q.push(make_pair(-1 * d[v], v));
}
}
}
}
int c[MAXN];
void dfs(int u) {
if (u == 1 || fa[u] == 1) c[u] = u;
else c[u] = c[fa[u]];
for (int i = head2[u]; i; i = edge2[i].nxt) {
int v = edge2[i].v;
dfs(v);
}
}
int main() {
freopen("burst.in", "r", stdin);
freopen("burst.out", "w", stdout);
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v;
ll w;
scanf("%d%d%lld", &u, &v, &w);
AddEdge(u, v, w), AddEdge(v, u, w);
}
Dijkstra(1);
for (int i = 2; i <= n; ++i) AddEdge2(fa[i], i);
dfs(1);
ll ans = INF;
for (int u = 1; u <= n; ++u) {
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].v;
ll w = edge[i].w;
if (fa[u] == v || fa[v] == u) continue;
if (c[u] == c[v]) continue;
ans = min(ans, d[u] + d[v] + w);
}
}
if (ans == INF) printf("-1\n");
else printf("%lld\n", ans);
cnt = cnt2 = 0;
for (int i = 1; i <= n; ++i) head[i] = head2[i] = 0;
}
return 0;
}
|