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

Download