台州做网站优化哪家好/爱站网长尾关键词挖掘查询工具

就是说给你个图，

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

用数字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");elseprintf("%d",ans);
}
int main()
{init();work();
}