首页 > 代码库 > poj 3767 I Wanna Go Home 最短路spfa
poj 3767 I Wanna Go Home 最短路spfa
题意:
给一个无向图,每个点有属性支持A或B(点1的属性恒为A,点2恒为B),求点1到点2的最短路,所求的最短路径要满足要求:路径上的边两边的点的属性至多有一次不一样。
分析:
最短路问题就用spfa水吧~~d[v][0]表示从起点开始到v点的属性没有变化过,d[v][1]表示从起点到v属性已经变化过了,最后答案min(d[2][0].d[2][1]);
代码:
//poj 3767 //sep9 #include <iostream> #include <queue> using namespace std; const int maxN=698; const int maxM=20024; struct Edge{ int v,w,next; }edge[maxM]; struct Node { int u,s; }; int n,e; int head[maxN]; int camp[maxN],inq[maxN][2],d[maxN][2]; void addedge(int u,int v, int w) { edge[e].v=v;edge[e].w=w,edge[e].next=head[u]; head[u]=e++; } void spfa() { queue<Node> Q; int i; memset(inq,0,sizeof(inq)); for(i=1;i<=n;++i) d[i][0]=d[i][1]=INT_MAX; d[1][0]=0; inq[1][0]=1; Node x; x.u=1,x.s=0; Q.push(x); while(!Q.empty()){ Node x=Q.front();Q.pop(); int u=x.u,s=x.s; inq[u][s]=0; for(i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v,w=edge[i].w; if(camp[u]==camp[v]){ if(d[v][s]>d[u][s]+w){ d[v][s]=d[u][s]+w; if(!inq[v][s]){ Node x; x.u=v,x.s=s; inq[v][s]=1; Q.push(x); } } }else{ if(s==0&&d[v][1]>d[u][0]+w){ d[v][1]=d[u][0]+w; if(!inq[v][1]){ Node x; x.u=v,x.s=1; inq[v][1]=1; Q.push(x); } } } } } } int main() { while(scanf("%d",&n)==1&&n){ e=0; memset(head,-1,sizeof(head)); int i,m; scanf("%d",&m); while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } for(i=1;i<=n;++i) scanf("%d",&camp[i]); int ans; spfa(); ans=min(d[2][0],d[2][1]); if(ans==INT_MAX) printf("-1\n"); else printf("%d\n",ans); } return 0; }
poj 3767 I Wanna Go Home 最短路spfa
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。