#include<bits/stdc++.h>

using names

........................................................................

该题解等待再次审核

........................................................................(剩余 292 个中英字符)

先说结论：

本题泛用性强，对策性一般，属于中杯偏下难度

（？）

P个点（不是N，别弄错了）），C条边，把奶牛当成点的权值，求所有点到一个点的最短距离与权值的乘积和

很标准的带权最短路问题，像是Dijkstra（需要堆优化）、Floyd（无向图优化）、SPFA什么的都可以）

因为不会Dijkstra的堆优化和SPFA遂写了Floyd（但是特别慢）（O((P^3)/2)）

#include<iostream>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
int n,p,m;
int pt1[810]; //奶牛所在节点 
int gra[810][810]; //邻接矩阵 
void f(){
	for(int k=1;k<=p;k++){
		for(int i=1;i<=p;i++){
			for(int j=1;j<i;j++){ //无向图，A到B和B到A一样，可以只算一半 
				if(gra[i][j]>gra[i][k]+gra[k][j]){
					gra[i][j]=gra[i][k]+gra[k][j];
					gra[j][i]=gra[i][j];
				}
			}
		}
	}	
}	
int main(){
	freopen("butter.in","r",stdin);
	freopen("butter.out","w",stdout);
	
	memset(gra,0x3f,sizeof gra); //初始化 
	
	scanf("%d%d%d",&n,&p,&m);
	for(int i=1;i<=n;i++){
		int k;scanf("%d",&k);
		pt1[k]++; //奶牛节点 
	}
	
	for(int i=1;i<=m;i++){
		int a,b,k;scanf("%d%d%d",&a,&b,&k);
		gra[a][b]=gra[b][a]=k;
	}
	
	for(int i=1;i<=p;i++) gra[i][i]=0; //到自身距离为0 
	f(); //Floyd 
	
	int ans=0x3f3f3f3f;
	for(int i=1;i<=p;i++){
		int sum=0;
		for(int j=1;j<=p;j++) sum+=gra[j][i]*pt1[j]; //用距离乘这个节点的奶牛数量，就是这个节点奶牛走的总距离 
		ans=min(ans,sum);
	}
	printf("%d",ans);
	
	return 0;
}

2024.7.19更新：

洛谷上一组数据卡了我半天 原因是：这个图不联通

所以应该在算ans的地方加个特判，这样才能过洛谷的数据）

if(gra[j][i]==0x3f3f3f3f&&pt1[j]) break;

小杯理解 逃逸了）

#include <iostream>

using namespace std;

int n,m,num=0;

int bz[100][100];

int dx[4]={-1,0,1,0},

   dy[4]={0,1,0,-1};

void doit(int p,int q){

........................................................................

该题解等待再次审核

........................................................................(剩余 1205 个中英字符)

#include<bits/stdc++.h>

using namespace std;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int sum=0,m,n,xb[100][100];

void doit(int p,int q)

{

int x,y,t,w,i;

in

........................................................................

该题解等待再次审核

........................................................................(剩余 1247 个中英字符)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define x first

#define y second

using namespace std;

typedef pair<char,char> PCC;

const int N

........................................................................

该题解等待再次审核

........................................................................(剩余 1591 个中英字符)

2024.7.14题解