某岛

… : "…アッカリ～ン . .. . " .. .

October 4, 2014

PKU Campus 2011

Problem B. A Problem about Tree

离线 + dfs()

const int N = int(1e4) + 9, M = int(1e4) + 9;
int fa[N]; VI todo[N], adj[N]; int path[N];
int n, m;
 
int vis[N];
 
struct qry{
    int u, r, z;
    void in(){
        z = -1;
        scanf("%d %d", &u, &r);
    }
    void out(){
        if (z == -1) z = fa[r];
        printf("%d\n", z);
    }
} Q[M];
 
 
void dfs(int u = 1){
 
    vis[u] = 1;
 
    ECH(it, todo[u]){
        int id = *it, r = Q[id].r;
        Q[id].z = vis[r] == 1 ? path[r] : -1;
    }
 
 
    ECH(it, adj[u]){
        int v = *it; if (v != fa[u]){
            fa[v] = u;
            path[u] = v;
            dfs(v);
        }
    }
 
    vis[u] = 0;
}
 
 
 
int main(){
 
    //freopen("e.txt", "r", stdin);
 
    int T; cin >> T; while (T--){
 
        cin >> n >> m;
        REP_1(i, n) todo[i].clear(), adj[i].clear();
 
        DO(n-1){
            int a, b; scanf("%d %d", &a, &b);
            adj[a].PB(b);
            adj[b].PB(a);
        }
 
        REP(i, m){
            Q[i].in();
            todo[Q[i].u].PB(i);
        }
 
        dfs();
        REP(i, m) Q[i].out();
    }
}

Dijkstra + Dp

const int N = int(5e2) + 9;
 
vector<PII> adj[N]; int pre[N];
int d[N][N];
int n, m;
 
priority_queue<PII, vector<PII>, greater<PII> > Q;
 
void Dijkstra(int d[], int s){
 
    fill(d, d+n, INF); d[s] = 0; Q.push(MP(0, s));
 
    while (!Q.empty()){
        int u = Q.top().se, du = Q.top().fi; Q.pop(); if (du != d[u]) continue;
 
        ECH(it, adj[u]){
            int v = it->fi, w = it->se;
            if (d[v] > d[u] + w){
                d[v] = d[u] + w;
                Q.push(MP(d[v], v));
            }
        }
    }
}
 
int dp[2][N][N];
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    while (~scanf("%d %d", &n, &m)){
        ++n; REP(i, n) adj[i].clear();
 
        REP(i, m){
            int a, b, c; scanf("%d %d %d", &a, &b, &c);
            if (a == b) continue;
            adj[a].push_back(make_pair(b, c)); swap(a,b);
            adj[a].push_back(make_pair(b, c));
        }
 
        REP(i, n) Dijkstra(d[i], i);
        int p = 0, q = 1; swap(p, q); FLC(dp[p], 0x3f); dp[p][0][0] = 0;
 
        FOR(i, 1, n){
            swap(p, q); int a = i-1; FLC(dp[p], 0x3f);
#define u dp[q][b][c]
            REP(b, n) REP(c, n) if (u != INF){
                checkMin(dp[p][b][c], u + d[a][i]);
                checkMin(dp[p][a][c], u + d[b][i]);
                checkMin(dp[p][a][b], u + d[c][i]);
            }
        }
 
        int z = INF; REP(i, n) REP(j, n) if (dp[p][i][j] != INF){
            checkMin(z, dp[p][i][j] + d[n-1][0] + d[i][0] + d[j][0]);
        }
        cout << z << endl;
    }
}

Posted by xiaodao
Category: 日常

某岛

PKU Campus 2011

Archives

Blogroll

Links

Myself

Project