3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 58这题迪杰斯特拉算法和弗洛伊德都会超时，这时要用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;
}
不知道为什么用双向队列可以快很多。。