Source: Luogu P1828, JZOJ #316

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[1000][1000];
int sum[1000];
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;
int linkk[1500],dis[1500],vis[1500],q[10000],a[1500];
struct node
{
	int y,v,next;
}e[5005];
void insert(int x,int y,int v)
{
	e[++t].y=y; e[t].v=v;
	e[t].next=linkk[x]; linkk[x]=t; 
}
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;
	int head=1,tail=1;
	q[head]=k;  //Point k Entry
	for (head=1;head<=tail;head++)
	{
		int x=q[head];  //Remove the team leader
		for (int i=linkk[x];i>0;i=e[i].next)  //Adjacency table query
		{
			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(xx,yy,vv);  //Adjacency table storage
		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;
}