PWALK - Dạo chơi đồng cỏ

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#define tr(v,it) for(typeof((v).begin())it=(v).begin(),_e=(v).end();it!=_e;++it)
const int N = 1005;

vvii g;
int d[N][N], n, q;
bool vst[N];

void bfs(int u) {
    queue<int> qu; d[u][u] = 0; fill(vst, vst+n, 0); vst[u] = 1;
    qu.push(u);
    while( !qu.empty() ) {
        int v = qu.front(); qu.pop();
        tr(g[v], it) {
            int w = it->first, l = it->second;
            if(vst[w] == 0) {
                d[u][w] = d[u][v] + l;
                vst[w] = 1;
                qu.push(w);
            }
        }
    }
}

int main() {
    //freopen( "inp", "r", stdin );
    scanf( "%d%d", &n, &q ); g = vvii(n, vii());
    for(int u, v, l, i = 1; i < n; ++i ) {
        scanf( "%d%d%d", &u, &v, &l );
        g[--u].push_back(ii(--v, l));
        g[v].push_back(ii(u,l));
    }
    for(int i = 0; i < n; ++i) bfs(i);
    for(int u, v, i = 0; i < q; ++i) {
        scanf( "%d%d", &u, &v );
        printf( "%d\n", d[--u][--v]);
    }
    return 0;
}

Download