引言
最的在做一本通网站上的题目,各种超时让人有些烦恼。今天一大早就做一本通网站1378题(http://ybt.ssoier.cn:8088/problem_show.php?pid=1378),一看数据规模不大(n=80),便随手写起来。先来一个SPFA吧,这几天觉得这算法还不错,代码也很快出来了。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
//1378:最短路径(shopth) #include<iostream> #include<cstdio> using namespace std; const int N=81; const int inf=1e9; int link[N][N],msg[N][N],dis[N],p[N],n,s; int que[N*2],h=0,t=1,cx,tx; int read() { int x=0,f=1,cnt=0; char ch='