TOJ 5098 Sweet Butter Spfa

野性酷女 2022-05-18 05:51 77阅读 0赞

## **5098: Sweet 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 luxuries for 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 that 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.

**输入**

*  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).

**输出**

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

**样例输入**

3 4 5  
2  
3  
4  
1 2 1  
1 3 5  
2 3 7  
2 4 3  
3 4 5

**样例输出**

题意：输入N,P,C，有N头牛，在P个牧场，有C条路。问所有牛到某一个牧场的路程最小是多少，遍历牧场1-P，计算min。

用dijstra做超时了，改用Spfa就AC了。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #define ll long long
    #define N 1005
    #define inf 0x3f3f3f3f
    using namespace std;
    int n,p,c,pos[1005];
    int head[1005],cnt,d[1005],vis[1005];
    struct edge{
        int to,next,w;
    }e[3000];
    void add(int u,int v,int w)
    {
        e[cnt].to=v;
    	e[cnt].next=head[u];
    	e[cnt].w=w;
        head[u]=cnt++;
    }
    struct qnode
    {
        int v,c;
        int operator<(const qnode& r)const{
            return c>r.c;
        }
    };
    int spfa(int s)
    {
    	priority_queue<qnode>que;
        for(int i=1;i<=p;i++)
    	{
    		d[i]=inf;
    		vis[i]=0;
    	}
        
        while(!que.empty())
    		que.pop();
        d[s]=0;
    	qnode q;
    	q.v=s;q.c=0;
        que.push(q);
        while(!que.empty())
    	{
            int u=que.top().v;
            que.pop();
            if(vis[u])continue;
            vis[u]=1;
            for(int i=head[u];~i;i=e[i].next)
    		{
                int v=e[i].to,w=e[i].w;
                if(!vis[v]&&d[v]>d[u]+w)
    			{
                    d[v]=d[u]+w;  
    				q.v=v;
    				q.c=d[v];             
                    que.push(q);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
    	ans+=d[pos[i]];
        return ans;
    }
    int main()
    {
    	int u,v,w,i,j,t,s; 
        memset(head,-1,sizeof head);
        scanf("%d%d%d",&n,&p,&c);
        for(i=1;i<=n;i++)
    	scanf("%d",&pos[i]);
        for(i=1;i<=c;i++)
    	{
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        s=inf;
        for(i=1;i<=p;i++)
    	{
            t=spfa(i);
            s=min(s,t);
        }
        printf("%d\n",s);
        return 0;
    }