poj 3767 I Wanna Go Home

题意：n个点(从1-n编号)

m条边

下面m行 u v dis 表示双向边u v的距离

n个点表示每个点被势力1或2占据

这里保证1 城市由势力1占据，2城市由势力2占据

思路：

求2遍spfa()

从1城市开始求所有走到所有都是势力1的城市的距离，存在d[1]数组中，d[1][ i ] 表示经过 i 城市任意都是势力1占领的城市的点能到达 1点的最短距离

再由2城市跑一遍spfa ，求出 2势力占领的距离2 城市最近的距离

最后ans=Min(ans, d[ 1 ] [ i ] + d[ 2 ] [ j ] + dis[ i ][ j ] )

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

#define N 605

#define INF 99999999

using namespace std;

struct node{

	int to,nex;

}edge[20005];

int edgenum,head[N];

int dis[N][N],n,ans;

int zhen[N],d[3][N];

bool inq[N];

inline int Min(int a,int b){return a>b?b:a;}

void addedge(int u,int v){

	edge[edgenum].to=v;

	edge[edgenum].nex=head[u];

	head[u]=edgenum++;

}

void spfa(int x,int other){

	for(int i=1;i<=n;i++)d[x][i]=INF;

	queue<int>q;while(!q.empty())q.pop();

	memset(inq,0,sizeof(inq));

	d[x][x]=0;

	q.push(x); inq[x]=1;

	while(!q.empty())

	{

		int u=q.front();q.pop(); inq[u]=0;

		for(int i=head[u];i!=-1;i=edge[i].nex)

		{

			int v=edge[i].to;

			if(zhen[u]==zhen[v] && d[x][v]>d[x][u]+dis[u][v] )

			{

				d[x][v]=d[x][u]+dis[u][v];

				if(!inq[v] && v!=other)

					inq[v]=true, q.push(v);

			}

		}

	}

}

int main(){

	int i,m;

	while(scanf("%d",&n),n)

	{

		scanf("%d",&m);

		memset(head,-1,sizeof(head)); memset(dis,-1,sizeof(dis));

		edgenum=0;

		while(m--){

			int u,v,dd;

			scanf("%d%d%d",&u,&v,&dd);

			if(dis[u][v]==-1)//去重边

				addedge(u,v),addedge(v,u),dis[u][v]=dis[v][u]=dd;

			else dis[u][v]=dis[v][u]=Min(dis[u][v],dd);

		}

		for(i=1;i<=n;i++)scanf("%d",&zhen[i]);

		ans=INF;

		spfa(1,2);

		spfa(2,1);

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

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

				if(zhen[i]!=zhen[j] && dis[i][j]!=-1)

					ans=Min(ans,d[1][i]+d[2][j]+dis[i][j]);

			if(ans>INF/2)ans=-1;

			printf("%d\n",ans);

	}

	return 0;

}

巴特西

poj 3767 I Wanna Go Home

最新文章

热门文章