| 记录编号 |
326047 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[USACO Oct08] 牧场旅行 |
最终得分 |
100 |
| 用户昵称 |
 Lethur |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.255 s |
| 提交时间 |
2016-10-20 19:14:05 |
内存使用 |
3.76 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
const int maxn=0x7ffff;int n,m,x,y,z,r;int dis[1005][1005],vis[1005];struct Edge{ int from,to,dist; Edge(int u,int v,int d):from(u),to(v),dist(d){}};using namespace std;vector<Edge>edges;vector<int>G[1005];queue<int> q;inline void add(int u,int v,int d){ edges.push_back((Edge){u,v,d}) ; r=edges.size() ; G[u].push_back(r-1); edges.push_back((Edge){v,u,d}) ; r=edges.size() ; G[v].push_back(r-1);}inline void spfa(int s){ memset(vis,0,sizeof(vis)); for(int i=0;i<=n;i++)dis[s][i]=maxn; dis[s][s]=0; vis[s]=1; q.push(s); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int i=0;i<G[u].size();i++){ Edge& e=edges[G[u][i]]; if(dis[s][u]<maxn&&dis[s][e.to]>dis[s][u]+e.dist){ dis[s][e.to]=dis[s][u]+e.dist; if(!vis[e.to]) { q.push(e.to); vis[e.to]=1; } } } }}int main(){ freopen("pwalk.in","r",stdin); freopen("pwalk.out","w",stdout); cin>>n>>m; for(int i=1;i<=n-1;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } for(int i=1;i<=n;i++){ spfa(i); } for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); printf("%d",dis[x][y]); if(i!=m)printf("\n"); } return 0;}