首页 > 代码库 > 186. [USACO Oct08] 牧场旅行

186. [USACO Oct08] 牧场旅行

186. [USACO Oct08] 牧场旅行(点击转到COGS)

   输入文件: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 2

2 1 2

4 3 2

1 4 3

1 2

3 2

输出格式:

?     第1..Q行:行i包含第i个询问的答案。

输出样例:

2

7

输出说明:

询问1:牧场1和牧场2的路径长度为2。 询问2:3->4->1->2;总长为7。

思路:

最短路径(用的spfa,反正我的floyd会超时)

#include<cstdio>
#include<cstring>
#define N 1010
using namespace std;
int n,q,p1,p2,ai,bi;
int dis[N],map[N][N];
bool vis[N];
void spfa(int x)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    int que[N],q,head=0,tail=1;
    que[head]=x;
    vis[x]=1;
    dis[x]=0;
    while(head<tail)
    {
        q=que[head++];
        vis[q]=0;
        for(int i=1;i<=n;i++)
          if(dis[i]>dis[q]+map[q][i])
          {
              dis[i]=dis[q]+map[q][i];
              if(!vis[i])
              {
                  que[tail++]=i;
                  vis[i]=1;
            }
          }
    }
}
int main()
{
    freopen("pwalk.in","r",stdin);
    freopen("pwalk.out","w",stdout);
    scanf("%d%d",&n,&q);
    int distance;
    memset(map,0x7f,sizeof(map));//用两层循环超时== 还是用memset
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&ai,&bi,&distance);
        map[ai][bi]=map[bi][ai]=distance;
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&p1,&p2);
        spfa(p1);
        printf("%d\n",dis[p2]);
    }
    fclose(stdin);fclose(stdout);
    return 0;
}

 

186. [USACO Oct08] 牧场旅行