思考
题目是思考N头牛都去一个点的最小路程是多少？ 我们可以转化一下 一个点让N头牛来走的最小路径是多少？
如果用Floyd去写，会发现题目是一个稀疏图。很大可能TLE，所以只能用SPFA求 每一个点到其他有牛的点的花费。
详情看代码注释
#include#include #include #include using namespace std;const int MAXN=5005;int n,p,c,cow[MAXN],head[MAXN],dis[MAXN],vis[MAXN],Count,sum,MIN=99999999;queue Q;//链式前向星存图 struct node{ int u,v,w,next; node() {} node(int _u,int _v,int _w,int _next){ u = _u,v = _v, w = _w,next = _next; }}G[MAXN];void AddEdge(int u,int v,int w){ G[Count] = node(u,v,w,head[u]); head[u] = Count++;}void spfa(int x){ memset(dis,63,sizeof(dis)); //记得初始化 memset(vis,0,sizeof(vis)); dis[x]=0; vis[x]=1; Q.push(x); while(!Q.empty() ){ int u = Q.front(); Q.pop(); for(int i=head[u];i!=-1;i=G[i].next){ int v = G[i].v; if(dis[v]>dis[u]+G[i].w){ dis[v]=dis[u]+G[i].w; if(!vis[v]){ vis[v] = 1; Q.push(v); } } } vis[u]=0; } sum=0; //有可能一个点上有很多头牛，但是他们的路程相对独立。 for(int i=1;i<=p;i++) sum=sum+cow[i]*dis[i]; MIN=min(MIN,sum); //维护一个最小值 return;}int main(){ memset(head,-1,sizeof(head)); scanf("%d%d%d",&n,&p,&c); for(int i=1;i<=n;i++) { int fuck; scanf("%d",&fuck); cow[fuck]++; } for(int i=1;i<=c;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); AddEdge(x,y,z); AddEdge(y,x,z); } for(int i=1;i<=p;i++){ spfa(i); } printf("%d\n",MIN);}