P1342 请柬

题面

思路：挺裸的最短路。

首先从\(1\)号站点到其他的站点的最小花费很容易想到单源最短路。

那么从其他站点返回\(1\)号站点的最小花费呢？从每个终点站点跑一遍Dijkstra吗？

不不不，首先从时间复杂度上就不对，时间复杂度基本上是\(O(n^2logn)\)的，而我们的\(n\)为\(1e6\)，明显不可以。

我们考虑反向建边，从\(1\)号点跑两边Dijkstra。

为什么要反向建边，仔细想想，不难，我们从起点出发顺着边走可以到达其他点，那么我们把边反过来，再顺着走，不就相当于从其他点到起点吗。感性理解一下？？

啊实在不行照着下面的图自己手玩一遍？？这样更形象更具体。

画图来形象的理解一下qwq：

这是未反向建边的原图：

从\(1\)号点可以跑Dijkstra即可求出到其他点的最小花费。

反向建边后的图：

这个时候我们从\(1\)号点跑Dijkstra，所求出的到其他点的最小花费，不正是其他点返回\(1\)号点的最小花费嘛。

感觉反向建边是最短路和一些其他问题差不多都是图论问题？？中挺常用的思路的。

啊对还要注意开long long，不然会爆int。分析一下？

一共\(1e6\)条边，每条边的极限权值为\(1e9\)，来回一趟极限值差不多为\(2e15\)，而int的极限值为\(2147483647\)差不多是\(2e9\)，已经爆了int了。

其实我们应该养成理性分析的习惯，不要等OJ返回WA的时候才恍然大悟：哦，这道题要开long long！这句话才不是在说我呢qaq！！应该除了我没人犯这种错误吧orz。

代码：

#include <bits/stdc++.h>
using namespace std;

template<typename temp>void read(temp &x){
	x = 0;temp f = 1;char ch;
	while(!isdigit(ch = getchar())) (ch == ‘-‘) and (f = -1);
	for(x = ch^48; isdigit(ch = getchar()); x = (x<<1)+(x<<3)+(ch^48));
	x *= f;
}
template <typename temp, typename ...Args>void read(temp& a, Args& ...args){read(a), read(args...);}

const int maxn = 1e6+10;

int n, m;
long long ans, dis_to[maxn], dis_from[maxn], vis_to[maxn], vis_from[maxn];

vector<pair<int,int> > v_to[maxn], v_from[maxn];

void qwq(){return;}

void Dijkstra_to(){
	memset(dis_to, 0x3f, sizeof(dis_to));
	priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > >q;
	q.push(make_pair(0,1));
	dis_to[1] = 0;
	while (q.size()){
		int now = q.top().second, len = q.top().first;
		q.pop();
		if(vis_to[now]) continue;
		vis_to[now] = 1;
		for(int i = 0; i < v_to[now].size(); i ++){
			int to = v_to[now][i].first, length = v_to[now][i].second;
			if(dis_to[to] > len + length){
				dis_to[to] = len + length;
				q.push(make_pair(dis_to[to], to));
			}
		}
	}
	return qwq();
}

void Dijkstra_from(){
	memset(dis_from, 0x3f, sizeof(dis_from));
	priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > >q;
	q.push(make_pair(0,1));
	dis_from[1] = 0;
	while (q.size()){
		int now = q.top().second, len = q.top().first;
		q.pop();
		if(vis_from[now]) continue;
		vis_from[now] = 1;
		for(int i = 0; i < v_from[now].size(); i ++){
			int to = v_from[now][i].first, length = v_from[now][i].second;
			if(dis_from[to] > len + length){
				dis_from[to] = len + length;
				q.push(make_pair(dis_from[to], to));
			}
		}
	}
	return qwq();
}

signed main(){
	read(n, m);
	for(int i = 1, x, y, z; i <= m; i ++){
		read(x, y, z);
		v_to[x].push_back(make_pair(y,z));
		v_from[y].push_back(make_pair(x,z));
	}
	Dijkstra_to();
	Dijkstra_from();
	for(int i = 1; i <= n; i ++) ans += dis_to[i]+dis_from[i];
	printf("%lld", ans);
	return 0;
}

P1342 请柬

原文：https://www.cnblogs.com/Vanyun/p/13420345.html