刚刚调Johnson模板调了一节晚修（记录）

输出了一堆负的，看了半天没想明白算法哪里有问题，把数组全开long long了，还是负的

结果是

//...
const int inf = 0x3b9aca00;
//...
long long ans;
//...
for(int j=1;j<=n;j++)
{
	if(reached[i][j] && i!=j)
		ans += (dis[i][j] + h[j] - h[i]) * j; //罪魁祸首 
	else if(!reached[i][j] && i!=j)
		ans += 1000000000 * j;
}
//...

两个int相乘，结果同样为int，超过$2^{31} -1$照样会溢出。此处+=后面的表达式就溢出了。