首页 > 代码库 > sgu226Colored graph

sgu226Colored graph

就是说给你个图,

这个图的每天边都是有颜色的,

用数字1到3表示颜色。

现在要从第一个点走到最后一个点,

如果上一步走过的边与下一步要走的边

颜色不同,就可以走,

问你最少要走几步可以走到目标点。

不能走到的话输出-1。

我用最短路做。

本来只需要加个判断颜色就可以,

可是这个地方可以通过环走到

最后一个点。

面对这种特例,

我想不到办法。

于是用了某人的想法。


只会bellmanford,

于是就用这个算法。

将dis变成二维数组,第二维表示跟某点

相连最近的那条边的颜色。

每次松弛化的时候,枚举三种颜色,


如果枚举到的这条边的颜色与枚举到

的颜色不同,并且,

把这条边加入进来可以让路径变短,

就把这条边加入进来。

最后的话,枚举到最后一个点,三种颜色

的情况,也就是与最后一个点相连的

那个边的颜色情况,取最小值,

如果最小值大于40000,也就是大于

边的无穷大,就可以说明,

第一个点是无法到最后一个点的,

输出-1即可,否则输出最小值。

 

我的代码如下:

 

#include<cstring>
#include<iostream>
using namespace std;
int num_dot,num_side;
struct node
{
	int s,e,c;
}side[40010];
void init()
{
	scanf("%d%d",&num_dot,&num_side);
	for(int i=0;i<num_side;i++)
		scanf("%d%d%d",&side[i].s,&side[i].e,&side[i].c);
}
void work()
{
	bool flag;
	int dis[210][4];
	memset(dis,127,sizeof(dis));
	dis[1][1]=dis[1][2]=dis[1][3]=0;
	while(1)
	{
		flag=1;
		for(int i=0;i<num_side;i++)
		{
			for(int k=1;k<4;k++)
			{
				if(k!=side[i].c&&dis[side[i].e][side[i].c]>dis[side[i].s][k]+1)
					dis[side[i].e][side[i].c]=dis[side[i].s][k]+1,flag=0;
			}
		}
		if(flag)
			break;
	}
	int ans=0xfffffff;
	for(int i=1;i<4;i++)
		ans=min(ans,dis[num_dot][i]);
	if(ans>40000)
		printf("-1");
	else
		printf("%d",ans);
}
int main()
{
	init();
	work();
}