这题迪杰斯特拉算法和弗洛伊德都会超时，这时要用SPFA算法，SPFA有点像bfs，用队列来实现，首先将所有节点dis置为INF，把自身节点dis置为0，把第一个点入队列，然后与他临接的点进行松弛操作，如果可以进行，查看改点是否在队列中，不在则加入队列，当队列为空则完成最短路，遍历一遍节点就可以得出答案
代码：
#include<algorithm> #include<iostream> #include<cstring> #include<stdio.h> #include<math.h> #include<string> #include<stdio.h> #include<queue> #include<stack> #include<map> #include<deque> using namespace std; const int INF=100861111; int p[805][805];//存图 int dis[805];//存单源点的距离 int vis[805];//存点有没有在队列中 int a[805][1455];//存点连接的点坐标 int num[805];//存点通往的点的数目 int cow[505];//存奶牛的标号 int n,m,c; queue<int>q; int minn; int spfa(int x) { int i,j,k; memset(vis,0,sizeof(vis)); for(i=1;i<=m;i++) { dis[i]=INF;//初始化为都不连通状态 } dis[x]=0;//注意 q.push(x); vis[x]=1; int now; while(!q.empty())//进行spfa算法 { now=q.front(); q.pop(); vis[now]=0; for(i=0;i<num[now];i++) { if(dis[now]+p[now][a[now][i]]<dis[a[now][i]])//进行松弛操作 { dis[a[now][i]]=dis[now]+p[now][a[now][i]]; if(!vis[a[now][i]]) { vis[a[now][i]]=1; q.push(a[now][i]); } } } } int sum=0; for(i=0;i<n;i++) { sum+=dis[cow[i]]; } return sum; } int main() { int i,j,k,x,y,v; while(scanf("%d%d%d",&n,&m,&c)!=EOF) { minn=INF; memset(num,0,sizeof(num)); for(i=1;i<=m;i++)//赋值 { for(j=1;j<=m;j++) { p[i][j]=INF; } } for(i=0;i<n;i++) { scanf("%d",&cow[i]); } for(i=0;i<c;i++)//记录图的情况 { scanf("%d%d%d",&x,&y,&v); p[x][y]=v; p[y][x]=v; a[x][num[x]]=y; a[y][num[y]]=x; num[x]++; num[y]++; } for(i=1;i<=m;i++)//枚举所有点 { int t=spfa(i); if(minn>t) minn=t; } printf("%d\n",minn); } return 0; } ps：不知道为什么用双向队列可以快很多。。
