首页 > 代码库 > 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(); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。