最短路裸题

题目大意:

拿到题目扫了一眼，大概出了个这样的思路：建个图，先以 1 1 1为源点跑一次最短路，再以除了 1 1 1以外的 n − 1 n-1 n−1个点为源点跑 n − 1 n-1 n−1次最短路。若不考虑某已死的算法（我们采用 d i j k s t r a dijkstra dijkstra），这种做法的时间复杂度为 Θ ( N 2 log ⁡ N ) \Theta(N^2\log{N}) Θ(N2logN)， q w q qwq qwq结果被 T \red{T} T上天了。后来又想到一个奇妙的性质：第二遍的 n − 1 n-1 n−1次 d i j k s t r a dijkstra dijkstra其实可以省去，我们以原图为基础建立反图，再在这个反图上以 1 1 1为源点跑一次最短路即可。最后一次扫描将答案累加即可。

还有一件比较有趣的事情：我在交不用堆优化的 d i j k s t r a dijkstra dijkstra时不放心开了 O 2 O_2 O2​,结果 M L E MLE MLE了三个点。不开优化又超时，最后靠数组的空间卡过去的。还是老老实实多打点代码吧。

A C   C o d e : \blue{AC \space Code:} AC Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
typedef long long LL;

int n,m,v[maxn];
LL ans,d[maxn],fd[maxn];
vector<int> ver[maxn],fver[maxn];
vector<LL> edge[maxn],fedge[maxn];

inline void read()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;LL w;
		cin>>u>>v>>w;
		ver[u].push_back(v);
		fver[v].push_back(u); 
		edge[u].push_back(w);
		fedge[v].push_back(w);
	}
}

inline void dijkstra()
{
	memset(v,0,sizeof(v));
	memset(d,0x3f,sizeof(d));
	
	d[1]=0;
	for(int i=1;i<n;i++)
	{
		int x=0;
		for(int j=1;j<=n;j++)
		{
			if(!v[j]&&(x==0||d[j]<d[x])) x=j;
		}
		v[x]=1;
		for(int y=0;y<ver[x].size();y++)
		{
			int t=ver[x][y];
			d[t]=min(d[t],d[x]+edge[x][y]);
		}
	}
}

inline void fdijkstra()
{
	memset(v,0,sizeof(v));
	memset(fd,0x3f,sizeof(fd));
	fd[1]=0;
	for(int i=1;i<n;i++)
	{
		int x=0;
		for(int j=1;j<=n;j++)
		{
			if(!v[j]&&(x==0||fd[j]<fd[x])) x=j;	
		}	
		v[x]=1;
		for(int y=0;y<fver[x].size();y++)
		{
			int t=fver[x][y];
			fd[t]=min(fd[t],fd[x]+fedge[x][y]);
		}
	}	
}

int main()
{
	ios::sync_with_stdio(false);
	read();
	dijkstra();
	fdijkstra();
	for(int i=2;i<=n;i++)
	{
		ans+=d[i];
		ans+=fd[i];
	}
	cout<<ans<<endl;
	return 0;
}