这个题目思路是很简单的,我们只需要枚举每个顶点作为目的地,然后再取其中距离总和最小的作为答案.开始的时候我用的是floyd一次就将所有点之间的最小距离求出来,但是超时了. 后面每次枚举一个点就用堆优化的dijkstral求一次这个点到其余点的最短路,这样就可以过了.算法中还用数组模拟了图的邻接矩阵.
代码如下:
/*ID: 15674811LANG: C++TASK: butter*/;p[maxn],d[maxn],first[maxn],vis[maxn];int u[maxn*10],v[maxn*10],w[maxn*10],next[maxn*10];int e,n,k,m;;void add_e(int x,int y,int z){u[e]=x; v[e]=y; w[e]=z;next[e]=first[x];first[x]=e++;}typedef pair<int,int>pii;priority_queue<pii,vector<pii>,greater<pii> >q;void dijkstral(int x){memset(vis,0,sizeof(vis));memset(d,0x3f,sizeof(d));d[x]=0;q.push(make_pair(d[x],x));while(!q.empty()){pii u=q.top(); q.pop();int x=u.second;if(vis[x]) continue;vis[x]=1;for(int k=first[x];k!=-1;k=next[k])if(d[v[k]]>d[x]+w[k]){d[v[k]]=d[x]+w[k];q.push(make_pair(d[v[k]],v[k]));}}}int main(){freopen(“butter.in”,”r”,stdin);freopen(“butter.out”,”w”,stdout);//freopen(“in.txt”,”r”,stdin);int sum=INF;scanf(“%d%d%d”,&k,&n,&m);for(int i=0;i<k;i++)scanf(“%d”,&p[i]);e=0;for(int i=1;i<=n;i++)first[i]=-1;for(int i=1;i<=m;i++){int x,y,z;scanf(“%d%d%d”,&x,&y,&z);add_e(x,y,z);add_e(y,x,z);}for(int i=1;i<=n;i++){dijkstral(i);int tmp=0,j;for(j=0;j<k;j++){if(d[p[j]]>=INF)break;tmp+=d[p[j]];}if(j>=k&&sum>tmp)sum=tmp;}printf(“%d\n”,sum); return 0;}
，每当我看天的时候我就不喜欢再说话，每当我说话的时候我却敢看天。
