POJ1511 Invitation Cards SPFA算法裸题变形

给出一个有向图，求出这个图从1到所有点的最短路径和所有点到1的最短路径的和。

这题数据量有点大，数据范围也大，所以用SPFA+邻接表做。

各种限制：Time Limit: 8000MS Memory Limit: 262144K（折腾评测机概念啊）

输入没什么处理的，注意在求所有点到1最短路径和的思想，嫑一看每个点都要是源点Floyd去了。。你想想，只要你把有向图所有箭头改一个方向，不又是从1到所有点的最短路径了么！？

废话不多说，贴代码！C++

这里我用了两个命名空间来防止重复，内容其实是一模一样的，（那我XX啊，直接一个类两个实例不就得了啊！不过这么写了就写了吧）用的STL的容器队列，SPFA，数组邻接表，会点SPFA都能看懂吧。好像是两秒多AC的，内存也不大。

因为数据范围太大，我们就用long long做的，不过为了省内存，我把不需要long long的地方都没有long long（我一同学除了_N用的int别的都用的long long，内存比我多）

//Accepted

#include <iostream>

#include <stdio.h>

#include <cstring>

#include <queue>

using namespace std;

const int MAXN=1000000+10;

struct Edge

{

	int v,w,next;

};

		int m,n;

namespace sp1

{

	Edge a[MAXN];

	int link[MAXN];

	bool visit[MAXN];

	long long d[MAXN];

	queue<int> q;

	void memoryset()

	{

		memset(a,0,sizeof(a));

		memset(link,0,sizeof(link));

		memset(visit,0,sizeof(visit));

		memset(d,0x3f,sizeof(d));

	}

	void add(int u,int v,int w)

	{

		static int tmp=1;

		a[tmp].v=v;

		a[tmp].w=w;

		a[tmp].next=link[u];

		link[u]=tmp;

		tmp++;

	}

	void spfa()

	{

		q.push(1);

		visit[1]=true;

		d[1]=0;

		while(!q.empty())

		{

			int x=q.front();

			q.pop();

			visit[x]=false;

			for(int i=link[x];i!=0;i=a[i].next)

			{

				if(d[x]+a[i].w<d[a[i].v])

				{

					d[a[i].v]=d[x]+a[i].w;

					if(visit[a[i].v]==false)

					{

						q.push(a[i].v);

						visit[a[i].v]=true;

					}

				}

			}

		}

	}

};

namespace sp2

{

	Edge a[MAXN];

	int link[MAXN];

	bool visit[MAXN];

	long long d[MAXN];

	queue<int> q;

	void memoryset()

	{

		memset(a,0,sizeof(a));

		memset(link,0,sizeof(link));

		memset(visit,0,sizeof(visit));

		memset(d,0x3f,sizeof(d));

	}

	void add(int u,int v,int w)

	{

		static int tmp=1;

		a[tmp].v=v;

		a[tmp].w=w;

		a[tmp].next=link[u];

		link[u]=tmp;

		tmp++;

	}

	void spfa()

	{

		q.push(1);

		visit[1]=true;

		d[1]=0;

		while(!q.empty())

		{

			int x=q.front();

			q.pop();

			visit[x]=false;

			for(int i=link[x];i!=0;i=a[i].next)

			{

				if(d[x]+a[i].w<d[a[i].v])

				{

					d[a[i].v]=d[x]+a[i].w;

					if(visit[a[i].v]==false)

					{

						q.push(a[i].v);

						visit[a[i].v]=true;

					}

				}

			}

		}

	}

};

int main()

{

	int _N;

	scanf("%d",&_N);

	while(_N--)

	{

		scanf("%d%d",&n,&m);

		sp1::memoryset();

		sp2::memoryset();

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

		{

			int a,b,c;

			scanf("%d%d%d",&a,&b,&c);

			sp1::add(a,b,c);

			sp2::add(b,a,c);

		}

		sp1::spfa();

		sp2::spfa();

		long long ans=0;

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

			ans+=sp1::d[i];

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

			ans+=sp2::d[i];

		cout << ans << endl;

	}

}

//以下是6月7号补充

我写了俩一模一样代码，注意是一模一样。。（猛的拍头）你不用一个类来封装啊！于是因为我懒就不写代码啦。。自己测了一下，一个SP的实例大小为25000296Bytes。。所以大家写的时候必须把SP的实例放全局，否则爆栈，否则爆栈，否则爆栈，否则爆栈，否则爆栈。。。

巴特西

POJ1511 Invitation Cards SPFA算法裸题变形

最新文章

热门文章