# Logu P1828 Sweet Butter (Graph Theory-Floyd/SPFA)

### Title Description

Farmer John found a way to make the sweetest butter in Wisconsin: sugar.Put the sugar on a pasture and he knows that N (1<=N<=500) cows will come to lick it, so he can make super sweet butter for a good price.Of course, he will pay extra for the cows.

Farmer John is cunning.Like Pavlov before, he knew he could train the cows to go to a specific ranch when they heard the bell.

He planned to put the sugar there and ring in the afternoon so that he could milk in the evening.Farmer John knows that each cow has its own favorite pasture (a pasture may not have only one cow).

Give the routes of the cattle between the pasture and the pasture, find the route and the shortest pasture for all the cattle (he will put the sugar there)

### Solving problems

• This graph topic can be solved by two shortest-path algorithms: FloydFloydFloyd and SPF SPFASPFASPFA.
• Let's start with FloydFloyd. Clearly, pure triple-loop enumeration is bound to explode, but there can be an optimization in the loop because this is an undirected graph. iii to jjj and jjj to iii are the same, so the third-loop jjjj enumeration to IIII is OK, so ACACAC can be done.
• There is also SPFASPFASPFA, in fact, this topic carries out ppp times SPFASPFA, enumerating each pasture as a concentrated point, summing up all the cattle's routes to reach the minimum value;

### Code Jun

##### Lovely Floyd:
```#include <bits/stdc++.h>
using namespace std;
int a;
int sum;
int main()
{
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
int n,m,c;
scanf("%d %d %d",&n,&m,&c);
for (int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[x]++;  //Count cattle numbers on Ranch x
}
memset(a,10,sizeof(a));  //initial value
for (int i=1;i<=c;i++)
{
int x,y,v;
scanf("%d %d %d",&x,&y,&v);
a[x][y]=min(a[x][y],v);  //Adjacency matrix stores multiple edges
a[y][x]=min(a[y][x],v);
}
for (int i=1;i<=m;i++) a[i][i]=0;  //initial value
for (int k=1;k<=m;k++)
for (int i=1;i<=m;i++)
for (int j=1;j<i;j++)
if (a[i][k]+a[k][j]<a[i][j])  //iteration
{
a[i][j]=a[i][k]+a[k][j];
a[j][i]=a[i][k]+a[k][j];
}
int ans=0xfffffff;
for (int i=1;i<=m;i++)
{
int s=0;
for (int j=1;j<=m;j++) s+=a[i][j]*sum[j];  //Accumulated distance
ans=min(ans,s);  //Minimum
}
printf("%d",ans);
return 0;
}
```
##### And then the handsome SPFA:
```#include <bits/stdc++.h>
using namespace std;
int t=0,n,p,c;
struct node
{
int y,v,next;
}e;
void insert(int x,int y,int v)
{
e[++t].y=y; e[t].v=v;
}
void SPFA(int k)  //SPFA Template
{
memset(dis,10,sizeof(dis));  //initial value
memset(vis,0,sizeof(vis));  //Empty the tag array, and vis[k] indicates whether point K is in the queue
dis[k]=0;
vis[k]=1;
{
{
if (dis[x]+e[i].v<dis[e[i].y])  //iteration
{
dis[e[i].y]=dis[x]+e[i].v;
if (vis[e[i].y]==0)  //If this point is not marked, mark, enter the team
{
vis[e[i].y]=1;
q[++tail]=e[i].y;
}
}
}
vis[x]=0;  //Queue
}
}
int main()
{
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
scanf("%d %d %d",&n,&p,&c);
for (int i=1;i<=n;i++) scanf("%d\n",&a[i]);
for (int i=1;i<=c;i++)
{
int xx,yy,vv;
scanf("%d %d %d",&xx,&yy,&vv);
insert(yy,xx,vv);  //Bi-directional side
}
int ans=0xfffffff;
for (int i=1;i<=p;i++)
{
SPFA(i);  //SPFA for each Ranch
int s=0;
for (int j=1;j<=n;j++) s+=dis[a[j]];  //Accumulated distance
ans=min(ans,s);  //Minimum
}
printf("%d",ans);
return 0;
}
```  Four original articles were published, 3 were praised, and 53 were visited

Added by rklapwijk on Mon, 03 Feb 2020 04:44:20 +0200