bzoj1603 / P2913 [USACO08OCT]车轮旋转Wheel Rotation

稳妥起见（防止数据出锅），用了bfs

每次的转移可以直接用异或和解决。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #define re register

 using namespace std;

 void read(int &x){

     char c=getchar();x=;

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

 }

 #define N 1002

 queue <int> h;

 int n,d[N]; bool vis[N];

 int cnt,hd[N],nxt[N<<],ed[N],poi[N<<],val[N<<];

 void adde(int x,int y,int v){

     nxt[ed[x]]=++cnt; hd[x]=hd[x]?hd[x]:cnt;

     ed[x]=cnt; poi[cnt]=y; val[cnt]=v;

 }

 int main(){

     read(n); int q1,q2,q3;

     for(re int i=;i<n;++i){

         read(q1);read(q2);read(q3);q3^=;//先取反，便于后面的异或

         adde(q1,q2,q3); adde(q2,q1,q3);

     }

     h.push(); d[]=; vis[]=;

     while(!h.empty()){

         int x=h.front(); h.pop();

         for(int i=hd[x];i;i=nxt[i]){

             int to=poi[i];

             if(!vis[to]){

                 d[to]=d[x]^val[i];

                 if(to==n){

                     printf("%d",d[n]);

                     return ;

                 }

                 vis[to]=;

                 h.push(to);

             }

         }

     }

 }