//这道题可以用迪杰特斯拉算法做,但是这道题我用的是SPFA算法, //记录一下关于链式向前星、spfa算法是怎么操作的, //spfa算法相比于迪杰特斯拉算法有很多优点,大家可以从网上搜索,很容易找到。 例题链接:https://vjudge.net/problem/HDU-2066 #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> typedef long long ll; using namespace std; #define inf 0x3f3f3f3f using namespace std; const int M=10005; struct sss { int v; //终点 int w; //边的权值 int next; }a[M<<1]; int head[M]; //head存储的是以i为起点,最后输入的那个编号 int vis[M],ven[M],nums[M]; //SPFS数组,vis记录最短路,ven记录是否在队列,nums记录入队次数 int cnt=0; //链式前向星数组 void add(int u,int v,int w)//链式前向星,加入节点 { a[cnt].v=v; a[cnt].w=w; a[cnt].next=head[u]; head[u]=cnt++; } bool SPFA(int s,int n) //从s点开始出发,一共n条边 { queue <int> q; memset(vis,inf,sizeof(vis)); //设s点到其余各个点的距离都是最大值 memset(ven,0,sizeof(ven)); //每一个点都不在队列中 memset(nums,0,sizeof(nums)); vis[s]=0; //初始化距离 ven[s]=1; //标记s在队列里面 nums[s]++;//队列次数+1 q.push(s); while(!q.empty()) { int x=q.front(); //以x点为翘板 q.pop(); //出队 ven[x]=0; //标记不在队列 for(int i=head[x]; i>=0; i=a[i].next) //遍历与x节点连通的点 { int y=a[i].v; //y是这条边的终点,以x为翘板,看初始点距离y点的距离可不可以更新 if(vis[y] > vis[x] + a[i].w) //如果 初始点距离终点的距离 > (初始点距离x的距离+i这条边的权值) ——> 更新 { vis[y] = vis[x] + a[i].w; if(ven[y]==0) //由于更新了节点,所以后续以这个为基础的最短路,也要更新下,所以如果在队列就不用加入,不在的话加入更新后续节点 { q.push(y); ven[y]=1;//标记这个节点在队列中 nums[y]++;//记录加入次数 if(nums[y]>n) return false; //如果这个点加入超过n次,说明存在负圈,直接返回 } } } } return true; } int main() { int n,m,t; int b[M],c[M]; while(cin >> n >> m >> t) //n为边数,m为初始的点的个数,t为目标点的个数 { cnt=0; memset(head,-1,sizeof(head)); //链式向前星里面的head数组初始化为-1 for(int i=0;i<n;i++) { int x,y,k; cin >> x >> y >> k; add(x,y,k); add(y,x,k); //双向边 } for(int i=0;i<m;i++) //与草儿家相连的城市,储存在b数组里面(也就是从这个点开始出发,m初始点的个数) { cin >> b[i]; } for(int i=0;i<t;i++) //草儿想去的地方,储存在c数组里面(也就是目的地,t为目标点的个数) { cin >> c[i]; } int minn=inf; for(int i=0;i<m;i++) //遍历多个找寻最小 { SPFA(b[i],n); for(int j=0;j<t;j++) { minn=min(minn,vis[c[j]]); } } cout << minn << endl; } }