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;
}