启发式算法，AC

回复 @0_0 :
因为最后一个测试点是一个环~~~~会爆栈~~~

为毛用树状数组？？？？？？
为了增加复杂度？？？？？

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

回复 @焦泽辉 :
= =

GS 果然强！！！

不想看到这一套题。。。。。。。。。。。。。。。。。。

　　

这是个很经典的二分图模型。以行为二分图的x部，列为二分图的y部。若格子(x, y)需要被消除，则连一条从x到y的边。最少次数即为二分图的最小点覆盖数。易证最小点覆盖数等于二分图的最大匹配数。
　　但是题目还要求代价尽量小。那么怎么办呢？实际上，最大匹配也可以当做最小割做。从源s向每个x部点连一条容量为1的边，从每个y部点向汇t连一条容量为1的边，而二分图的每条边容量设为+∞。一个割会使得s和t不连通，也就使得二分图的每条边的两个端点中至少有一个被选出。同时最小割是所有割中代价最小的。
　　提出这个模型的意义在于可以通过修改边的容量使得它能解决此题。我们考虑修改这个最小割模型的边的容量。将原来容量为1的边修改容量为10^6+ai(或bj)。由于数据范围中ai, bj<=100且n <= 100，所以∑ai+∑bj仍然远小于10^6。所以最小割必然是先满足删去的边尽量少，然后满足附加的容量和尽量小。
　　最小次数即等于新图最小割除以10^6的商，最小代价等于最小割模10^6的余数。如果用Dinic计算最小割，则时间复杂度是O(n4)。实际上最短增广路算法一般远远达不到理论复杂度，因此可以完美地解决这道题。

小cheat...

可以用单调队列哦！！

の ！！！！ 比A＋B 还 水~~~~~

树状数组基本操作！！！

打表秒过

STO 耶稣大神 ORZ
跪跪跪跪跪
跪　　　跪跪跪跪跪跪跪跪跪跪跪跪跪
跪　　　跪　　　跪　　　　　　跪
跪　　　跪　　　跪　　　　　跪
跪　　　跪　　　跪　　　　跪
跪跪跪跪跪　　　跪　　　跪跪跪跪跪
跪跪跪跪跪
跪　　　跪跪跪跪跪跪跪跪跪跪跪跪跪
跪　　　跪　　　跪　　　　　　跪
跪　　　跪　　　跪　　　　　跪
跪　　　跪　　　跪　　　　跪
跪跪跪跪跪　　　跪　　　跪跪跪跪跪

难道要维护两颗平衡树？？？？？？？？？？？？？？？？？？？？？？？？？？？？想想就不想打！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！（表示不会字符串hash）（不会用指针（没办法用trie（不知道开多大？？）））

回复 @乾坤兑 :
压位好写还是快速幂好写？？？

int main(){

 freopen("cruel1.in","r",stdin);

 freopen("cruel1.out","w",stdout);

 getnum(a);

 scanf("%d",&b);

 BIGNUM c; c.clean();

 c.x[1] = c.x[0] = 1;

 while (b){

 if (b & 1) c = a * c;

 a = a * a;

 b >>= 1;

 }

 print(c);

 return 0;

}

简短的主程序

回复 @Truth.Cirno :
为毛要用并查集？？？

回复 @HZOI_lhy111 :
不玩了。。。。