[Code+#4] 最短路 - 建图优化,最短路

最短路问题，然而对于任意\(i,j\)，从\(i\)到\(j\)可以只花费\((i xor j) \cdot C\)

对每个点\(i\)，只考虑到\(j\)满足\(j=i xor 2^k, j \leq i\)

显然其它边可以由这些边组合得到

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAX_NODE = 500005;

template <class T> class Graph_SP { // 解决单源最短路径问题

public:

	vector<pair<int, T> >G[MAX_NODE];

	int d[MAX_NODE], v[MAX_NODE]; // 距离表与访问标识表

	void make(int t1, int t2, T t3) { // 造边（有向）

		G[t1].push_back(make_pair(t2, t3));

	}

	void reset_graph(int n) { // 用于清除图邻接表

		for (int i = 0; i <= n; i++)

			G[i].clear();

	}

	void reset_solver(int n) { // 对距离表与访问标识表的清除 如果改变了类型，该函数可能需要重写！

		memset(d, 0x3f, sizeof d);

		memset(v, 0x00, sizeof v);

	}

	void solveDijkstra(int v0, int n) { // 执行主计算任务(使用Dijkstra)

		priority_queue<pair<T, int>, vector<pair<T, int> >, greater<pair<T, int> > >q;

		reset_solver(n); // 自动调用对距离表与访问标识表的清除

		d[v0] = 0;

		q.push(make_pair(0, v0));

		while (q.size()) {

			pair<T, int> p = q.top();

			T dis = p.first; // dis为到当前点的距离

			int pos = p.second; // pos为当前点

			q.pop();

			v[pos] = 1;

			for (int i = 0; i < G[pos].size(); i++) {

				int x = G[pos][i].first; // x为当前枚举边的终点，

				T y = G[pos][i].second; // y为当前枚举边的权值

				if (d[x] > d[pos] + y) {

					d[x] = d[pos] + y;

					if (!v[x])

						q.push(make_pair(d[x], x));

				}

			}

		}

	}

} ;

Graph_SP <int> g;

signed main() {

    int n,m,k,t1,t2,t3,a,b;

    scanf("%lld%lld%lld",&n,&m,&k);

    for(int i=1;i<=m;i++) {

        scanf("%lld%lld%lld",&t1,&t2,&t3);

        g.make(t1,t2,t3);

    }

    scanf("%lld%lld",&a,&b);

    for(int i=0;i<=n;i++) {

        for(int p=0;p<=20;p++) {

            int j=i^(1ll<<p);

            if(j<=n) g.make(i,j,k*(1ll<<p));

        }

    }

    g.solveDijkstra(a,n);

    cout<<g.d[b]<<endl;

}

巴特西

[Code+#4] 最短路 - 建图优化,最短路

最新文章

热门文章