[最短路]USACO 3.2.6 Sweet Butter 香甜的黃油 butter 解題報告

Farmer John has discovered the secret to making the sweetest butter in all of 

Wisconsin: sugar. By placing a sugar cube out in the pastures, he knows the N

 (1 <= N <= 500) cows will lick it and thus will produce super-sweet butter

 which can be marketed at better prices. Of course, he spends the extra money 

on luxuriesfor the cows.

FJ is a sly farmer. Like Pavlov of old, he knows he can train the cows to go to a 

certain pasture when they hear a bell. He intends to put the sugar there and 

then ring the bell in the middle of the afternoon so that the evening's milking 

produces perfect milk.

FJ knows each cow spends her time in a given pasture (not necessarily alone). 

Given the pasture location of the cows and a description of the paths the 

connect the pastures, find the pasture in which to place the sugar cube so

 that the total distance walked by the cows when FJ rings the bell is minimized. 

FJ knows the fields are connected well enough that some solution is 

always possible.


PROGRAM NAME: butter
INPUT FORMAT

Line 1: Three space-separated integers: N, the number of pastures: 
P (2 <= P <= 800), and the number of connecting paths:
 C (1 <= C <= 1,450).
 Cows are uniquely numbered 1..N. Pastures are uniquely numbered 1..P.
Lines 2..N+1: Each line contains a single integer that is the pasture number
 in which a cow is grazing. Cow i's pasture is listed on line i+1.
Lines N+2..N+C+1: Each line contains three space-separated integers that
 describe a single path that connects a pair of pastures and its length. 
Paths may be traversed in either direction. 
No pair of pastures is directly connected by more than one path. 
The first two integers are in the range 1..P; 
the third integer is in the range (1..225).

SAMPLE INPUT (file butter.in)
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
INPUT DETAILS
This diagram shows the connections geometrically:
P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4
OUTPUT FORMAT

Line 1: A single integer that is the minimum distance the cows must walk 
to a pasture with a sugar cube.

SAMPLE OUTPUT (file butter.out)
8
OUTPUT DETAILS:

Putting the cube in pasture 4 means: cow 1 walks 3 units; cow 2 walks 5
units; cow 3 walks 0 units -- a total of 8.

------------------------------------------------------------------------------------

描述

農夫John發現做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道N（1<=N<=500）只奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。當然，他將付出額外的費用在奶牛上。

農夫John很狡猾。像以前的Pavlov，他知道他可以訓練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那裏然後下午發出鈴聲，以至他可以在晚上擠奶。

農夫John知道每隻奶牛都在各自喜歡的牧場（一個牧場不一定只有一頭牛）。給出各頭牛在的牧場和牧場間的路綫，找出使所有牛到達的路程和最短的牧場（他將把糖放在那）

格式

PROGRAM NAME: butter

INPUT FORMAT:

(file butter.in)

第一行: 三個數：奶牛數N，牧場數（2<=P<=800），牧場間道路數C(1<=C<=1450)

第二行到第N+1行: 1到N頭奶牛所在的牧場號

第N+2行到第N+C+1行： 每行有三個數：相連的牧場A、B，兩牧場間距離D（1<=D<=255），當然,連接是雙向的

OUTPUT FORMAT:

(file butter.out)

一行 輸出奶牛必須行走的最小的距離和

SAMPLE INPUT

3 4 5

2

3

4

1 2 1

1 3 5

2 3 7

2 4 3

3 4 5

樣例圖形

P2  
P1 @--1--@ C1
    \    |\
     \   | \
      5  7  3
       \ |   \
        \|    \ C3
      C2 @--5--@
         P3    P4

SAMPLE OUTPUT

8

說明：

放在4號牧場最優

【分析】

圖論，多源最短路徑。由於節點數過大所以多源最短路算法Floyd無法使用，但由於圖比較稀疏，所以可以用SPFA算法就可以，經過堆優化的Dijkstra算法也可以快速滿分。

我寫了SPFA，使用鄰接表存儲。

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
int Map[1000][1000];
int Val[1000][1000];
int Abut[1000]={0};
int dist[1000][1000];
bool flag[1000]={0};
int Cow[1000]={0};
int C,N,M;
const int MAXN=2000000;

void spfa(int S)
{
    int q[10000];
    int h=0,t=1;
    int x,i;
    memset(q,0,sizeof(q));
    for (i=1;i<=N;i++)
    {
        dist[S][i]=MAXN;
        flag[i]=false;
    }
    dist[S][S]=0;
    q[t]=S;
    flag[S]=true;
    while(h<t)
    {
        h++;
        x=q[h];
        flag[x]=0;
        for(int i=1;i<=Abut[x];i++)
        {
            if(dist[S][Map[x][i]]-Val[x][i]>dist[S][x])
            {
                dist[S][Map[x][i]]=dist[S][x]+Val[x][i];
                if(!flag[Map[x][i]])
                {
                    t=t+1;
                    q[t]=Map[x][i];
                    flag[Map[x][i]]=true;
                }
            }
        }
    }
}

void init()
{
    scanf("%d %d %d\n",&C,&N,&M);
    int tmp;
    for (int i=1;i<=C;i++)
    {
        scanf("%d\n",&tmp);
        Cow[tmp]++;
    }
    int a,b,c;
    for (int i=1;i<=M;i++)
    {
        scanf("%d %d %d\n",&a,&b,&c);
        Abut[a]++;
        Map[a][Abut[a]]=b;
        Val[a][Abut[a]]=c;
       
        Abut[b]++;
        Map[b][Abut[b]]=a;
        Val[b][Abut[b]]=c;
    }
}

void work()
{
    for (int i=1;i<=N;i++)
        spfa(i);
    long long num=2000000000;
    //int pos=1;
    for(int i=1;i<=N;i++)
    {
        long long tmp=0;
        for (int j=1;j<=N;j++)
            tmp+=Cow[j]*dist[j][i];
        if(tmp<num)
        {
            num=tmp;
            //pos=i;
        }
    }
    int res=num;
    printf("%d\n",res);
}

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