SPFA —— 他死了啊

Posted by WildCow on November 8, 2018

写在前面



“测测你的 SPFA 能跑多快?”




内容



$3k + 1$ 个点 $5k$ 个边 访问 $1$ 号点 $2^k$ 次,不过这是针对之前的一份代码的,堆里会有相同的 $key$,然后按点编号从大到小还是从小到大顺序来着。。所以可能得调一下边权大小


#include <bits/stdc++.h>
#include 
#include 
#include 
#include 
#include 

typedef long long int64;

bool assert(const bool f)
{
​	if (!f)
​		std::cerr << "Error!" << std::endl;
​	return f;
}

struct edge_Tp
{
​	int v, w, c;
​	edge_Tp(const int _v, const int _w, const int _c) : v(_v), w(_w), c(_c) { }
};

class Graph
{
​	private:
​		std::vector P;
​		std::mt19937 engine;
​		
	public:
		int n, s;
		int64 sc;
		std::vector edge;
		
		Graph(const int _n) : P(_n), engine(19260817), n(_n), s(0), sc(0)
		{
			for (int i(0); i != n; ++i)
				P[i] = n - 1 - i;
			//std::shuffle(P.begin(), P.end(), engine);
		}
		
		void insert(const int v, const int w, const int c)
		{
			edge.emplace_back(v, w, c), sc += c;
		}
		
		void shuffle()
		{
			std::shuffle(edge.begin(), edge.end(), engine);
		}
		
		friend std::ostream &operator<<(std::ostream &, const Graph &);
};

inline std::ostream &operator<<(std::ostream &os, const Graph &g)
{
​	os << g.n << ' ' << g.edge.size() << ' ' << g.P[g.s] + 1 << '\n';
​	for (const auto &e : g.edge)
​	{
​		assert(0 <= e.v && e.v < g.n), assert(0 <= e.w && e.w < g.n);
​		os << g.P[e.v] + 1 << ' ' << g.P[e.w] + 1 << ' ' << e.c << '\n';
​	}
​	return os;
}

Graph generator(const int k)
{
​	Graph g(k * 3 + 1);
​	for (int i(0); i != k; ++i)
​	{
​		g.insert(i * 3, i * 3 + 1, 0);
​		g.insert(i * 3 + 1, i * 3 + 2, 0);
​		g.insert(i * 3, i * 3 + 2, (3 << (k - 1 - i)) - 1);
​		g.insert(i * 3 + 2, i * 3 + 3, 0);
​		g.insert(i * 3, i * 3 + 3, k - 1 == i ? 1 : 3 << (k - 2 - i));
​	}
​	//g.shuffle();
​	return g;
}

int main(int argc, char **argv)
{
​	Graph g(generator(25));
​	assert(g.n <= 100000 && g.edge.size() <= 200000 && g.sc <= 1000000000);
​	freopen("test.in", "wb", stdout);
​	std::cout << g;
​	
	return 0;

}