【题目描述】 有N个士兵，分布在多个据点，有的据点有可能多个士兵，有的据点有可能没有士兵。共有P个据点，据点间有C条双向道路。求将总部设在哪里，使得所有士兵回总部的路程和最小。 【输入格式】 第一行: 三个数：士兵数N，据点数（2<=P<=800），据点间道路数C(1<=C<=1450) 第二行到第N+1行: 1到N个士兵所在的据点号 第N+2行到第N+C+1行： 每行有三个数：相连的据点A、B，两据点间距离D（1<=D<=255） 【输出格式】 一个整数， 输出士兵回总部必须行走的最小的距离和。 【样例输入】
3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5【样例输出】
8【分析】 裸的SPFA板子题。
#include<bits/stdc++.h> using namespace std; const int maxn=800+5; int a[maxn][maxn],w[maxn][maxn]; bool v[maxn]; int dis[maxn],b[maxn],q[maxn*maxn]; int main(){ int n,p,c; cin>>n>>p>>c; for (int i=1;i<=n;i++) scanf("%d",&b[i]); for (int i=1;i<=c;i++){ int x,y; scanf("%d%d",&x,&y); scanf("%d",&w[x][y]); a[x][++a[x][0]]=y; a[y][++a[y][0]]=x; w[y][x]=w[x][y]; } int sum=(1<<31)-1; for (int i=1;i<=p;i++){ memset(dis,127/3,sizeof(dis)); memset(q,0,sizeof(q)); memset(v,0,sizeof(v)); dis[i]=0; q[1]=i; int h=0,t=1; v[i]=1; while (h<t){ h++; int u=q[h]; v[u]=0; for (int j=1;j<=a[u][0];j++){ if (dis[a[u][j]]>dis[u]+w[u][a[u][j]]){ dis[a[u][j]]=dis[u]+w[u][a[u][j]]; if (!v[a[u][j]]){ q[++t]=a[u][j]; v[a[u][j]]=1; } } } } int ans=0; for (int j=1;j<=n;j++) ans+=dis[b[j]]; sum=min(ans,sum); } cout<<sum; }