水题还★☆，好坑啊

水题没有一遍AC，我有愧于人民啊！

带“到根边权和”的并查集，解法真漂亮！

@digital-T 应该是有了STL后整个人都变懒了。

回复 @天一阁 :
你不觉得这个毛团萌萌哒么……

sort函数的cmp必须是全局函数或者static……也就是不能在不同的对象中让cmp有不同语义，杯具了一中午……

为何粘上这个图！！！

为什么图折磨恶心！

文件名的最后竟然是1，一直以为是l

回复 @省选完挂，OI再见 : 贴代码很不美观啊

单调队列不是O（n）吗QAQ

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 205
int map[N][N];
int n, m;
inline void floyd(){
for (int i = 1; i <= n; i ++) map[i][i] = 0;
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++){
if (i != k){
for (int j = 1; j <= n; j ++)
if (j !=i && j != k){
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}
}
}
}
int main(){
freopen("hardest.in", "r", stdin);
freopen("hardest.out", "w", stdout);
int T;
scanf("%d", &T);
while (T --){
memset(map, 0x3f, sizeof(map));
scanf("%d %d", &n, &m);
int x, y, z;
for (int i = 1; i <= m; i ++){
scanf("%d %d %d", &x, &y, &z);
map[x][y] = min(map[x][y], z);
map[y][x] = min(map[x][y], z);
}
floyd();
if (map[1][n] != 0x3f3f3f3f)
printf("%d\n", map[1][n]);
else printf("-1\n");
}
return 0;
}

注意longlong啊！！

请问管理员题目上传的时候测试文件怎么上传？@cstdio

记忆化秒过……碰到圈返回INF即可

果然我边界虽然考虑了但是还是写错了QAQ
蒟蒻长跪不起OTZZZZZZ

脑子无限秀逗

mark

回复 @cstdio :
这个证明，膜拜ORZZZZZ

╮(╯▽╰)╭，n和k打反害我挂了3次。

为什么我本地测试15会超时QAQ