WinterCamp2011_ProblemSet_Final.pdf

（… 工事中。。。）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int N = 101, M = 1001, D = 10001;

struct Edge{
    int p, w;
} E[N];
vector<int> adj[N];
int tot;

bool dp[N][D];
int n, m;

void AddEdge(int x, int y, int w){
    E[tot].p = y, E[tot].w = w;
    adj[x].push_back(tot++);
}

void dfs(int u, int s){
    if (dp[u][s]) return;
    dp[u][s] = true;

    int v, w;
    for (int i=0;i<adj[u].size();i++){
        v = E[adj[u][i]].p, w = E[adj[u][i]].w;
        dfs(v, s ^ w);
    }
}

void init(){
    cin >> n >> m;
    tot = 0;

    int x, y, w;
    for (int i=0;i<m;i++){
        cin >> x >> y >> w;
        AddEdge(x, y, w);
        AddEdge(y, x, w);
    }

    memset(dp, false, sizeof(dp));
}

void solve(){
    dfs(1, 0);
    for ( int i=D-1;i>=0;i--)
    if (dp[n][i]){
        cout << i << endl;
        return ;
    }
}

int main(){
    //freopen( "xor.in" , "r" , stdin ) ;
    //freopen( "xor.out", "w" , stdout) ;

    init(); solve();
}

Posted by xiaodao
Category: 日常