186. [USACO Oct08] 牧场旅行
★★ 输入文件:pwalk.in
输出文件:pwalk.out
简单对比 时间限制:1 s 内存限制:128 MB
n个被自然地编号为1..n奶牛(1<=n<=1000)正在同样被方便的编号为1..n的n个牧场中吃草。更加自然而方便的是,第i个奶牛就在第i个牧场中吃草。
其中的一些对牧场被总共的n-1条双向通道的一条连接。奶牛可以通过通道。第i条通道连接的两个牧场是A_i和B_i(1<=A_i<=N;1<=B_i<=N)其长度是L_i(1<=L_i<=10000)。
通道只会连接两个不同的牧场,所以这些通道使得整个牧场构成了一棵树。
奶牛们是好交际的希望能够经常的访问别的奶牛。急切地,它们希望你能通过告诉它们Q(1<=Q<=1000)对牧场的路径来帮助他们安排旅行。(这里将有Q个询问,p1,p2(1<=p1<=n;1<=p1<=n))
分数:200
问题名称:pwalk
输入格式:
- 第1行:两个用空格隔开的整数:n和Q
- 第2..n行:第i+1行包含三个用空格隔开的整数:A_i,B_i和L_i
- 第n+1..N+Q行:每行包含两个用空格隔开的整数,代表两个不同的牧场,p1和p2
输入样例(file pwalk.in):
4 22 1 24 3 21 4 31 23 2
输出格式:
- 第1..Q行:行i包含第i个询问的答案。
输出样例:
27
思路:spfa算法。
1 #include2 #include 3 #define N 1010 4 using namespace std; 5 int n,q; 6 int dis[N],map[N][N]; 7 bool vis[N]; 8 int que[N]; 9 int head,tail,d;10 void spfa(int x)11 {12 memset(vis,0,sizeof(vis));13 memset(dis,0x3f,sizeof(dis));14 head=0;15 tail=0;16 que[tail++]=x;17 vis[x]=1;18 dis[x]=0;19 while(head dis[d]+map[d][i])25 {26 dis[i]=dis[d]+map[d][i];27 if(!vis[i])28 {29 que[tail++]=i;30 vis[i]=1;31 }32 }33 }34 }35 int main()36 {37 freopen("pwalk.in","r",stdin);38 freopen("pwalk.out","w",stdout);39 scanf("%d%d",&n,&q);40 memset(map,0x7f,sizeof(map));41 for(int i=1;i