PWALK - Dạo chơi đồng cỏ
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#include<queue>
#include<vector>
#define MAX 1111
#define INF 1e9
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int n,q;
int d[MAX][MAX];
vii g[MAX];
void loadgraph(void) {
scanf("%d",&n);
scanf("%d",&q);
int i,u,v,w;
for (i=1;i<n;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&w);
g[u].push_back(ii(v,w));
g[v].push_back(ii(u,w));
}
for (u=1;u<=n;u=u+1)
for (v=1;v<=n;v=v+1)
d[u][v]=INF;
}
void dijkstra(void) {
int i,u,v,w;
ii x;
for (u=1;u<=n;u=u+1) {
priority_queue<ii,vii,greater<ii> > q;
q.push(ii(0,u));
while (!q.empty())
{
x=q.top(); q.pop();
w=x.first;
v=x.second;
for (i=0;i<g[v].size();i=i+1)
if (d[u][g[v][i].first]>w+g[v][i].second) {
d[u][g[v][i].first]=w+g[v][i].second;
q.push(ii(w+g[v][i].second,g[v][i].first));
}
}
}
}
void process(void) {
int i,u,v;
for (i=1;i<=q;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
printf("%d\n",d[u][v]);
}
}
int main(void) {
loadgraph();
dijkstra();
process();
}