USACO月賽 Oct08 牧場旅行 pwalk

【問題描述】
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和c_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。

【分析】

這明明是一棵樹，直接廣搜即可過全數據，沒必要求最短路。用Floyd還會超時。

【代碼一：鄰接矩陣】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int QQ;
unsigned int Mat[1001][1001];

void print()
{
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=N;j++)
            cout<<Mat[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}

unsigned int Q[1002];
unsigned int K[1002];
bool used[1001];

unsigned  int bfs(int S,int E)
{
    for (int i=1;i<=N;i++)
        used[i]=true;
    used[S]=false;
   
    int rear=1;
    int head=0;
    Q[0]=S;
    K[0]=0;
    int T;
    while(head<=rear)
    {
        T=Q[head];
        if(T==E)
            return K[head];
        for (int i=1;i<=N;i++)
        {
            if(Mat[T][i]>0 && used[i])
            {
                Q[rear]=i;
                K[rear]=K[head]+Mat[T][i];
                //Mat[S][i]=K[rear];
                //Mat[i][S]=K[rear];
                used[i]=false;
                rear++;
            }
        }
        head++;
    }
    return K[rear];
}

void init()
{
    scanf("%d %d\n",&N,&QQ);
   
   
    int a,b,c;
    for (int i=1;i<=N-1;i++)
    {
        scanf("%d %d %d\n",&a,&b,&c);
        Mat[a][b]=c;
        Mat[b][a]=c;
    }
   
    //print();
   
    for(int i=1;i<=QQ;i++)
    {
        scanf("%d %d\n",&a,&b);
        printf("%d\n",bfs(a,b) );
    }
    return;
}



int main()
{
    freopen("pwalk.in","r",stdin);
    freopen("pwalk.out","w",stdout);
   
    init();
   
    return 0;
}

【代碼二：鄰接表】

#include <cstdio>
using namespace std;

int way[1001]={0},map[1001][1000]={{0}},dis[1001][1000]={{0}};

void bfs(int st,int en)
{
    int i,que[1000]={0},len[1000]={0},tail=0,head=0;
    bool used[1001]={false};
    que[0]=st;
    len[0]=0;
    used[st]=true;
    while (tail<=head)
    {
        for (i=0;i<way[que[tail]];i++)
            if (!used[map[que[tail]][i]])
            {
                head++;
                que[head]=map[que[tail]][i];
                len[head]=len[tail]+dis[que[tail]][i];
                used[que[head]]=true;
                if (que[head]==en)
                {
                    printf("%d\n",len[head]);
                    return;
                }
            }
        tail++;
    }
}

int main(void)
{
    freopen("pwalk.in","r",stdin);
    freopen("pwalk.out","w",stdout);
    int i,n,q,temp,temp2,temp3;
    scanf("%d %d\n",&n,&q);
    for (i=1;i<n;i++)
    {
        scanf("%d %d %d\n",&temp,&temp2,&temp3);
        map[temp][way[temp]]=temp2;
        map[temp2][way[temp2]]=temp;
        dis[temp][way[temp]]=temp3;
        dis[temp2][way[temp2]]=temp3;
        way[temp]++;
        way[temp2]++;
    }
    for (i=1;i<=q;i++)
    {
        scanf("%d %d\n",&temp,&temp2);
        bfs(temp,temp2);
    }
    fclose(stdin);
    fclose(stdout);
    return (0);
}