OJ题号：洛谷2935
思路：Floyd
1 #pragma GCC optimize ("O3") 2 #include<cstdio> 3 #include<cctype> 4 #define inf 0x7fffffff>>1 5 inline int min(const int a,const int b) { 6 return a<b?a:b; 7 } 8 inline int getint() { 9 int ch; 10 while(!isdigit(ch=getchar())); 11 int x=ch^'0'; 12 while(isdigit(ch=getchar())) x=((x+(x<<2))<<1)+(ch^'0'); 13 return x; 14 } 15 int main() { 16 int p=getint(),F=getint(),C=getint(); 17 int f[F]; 18 for(int i=0;i<F;i++) { 19 f[i]=getint(); 20 } 21 int c[p+1][p+1]; 22 for(int i=1;i<=p;i++) { 23 for(int j=1;j<=p;j++) { 24 c[i][j]=(i==j)?0:inf; 25 } 26 } 27 for(int i=0;i<C;i++) { 28 int a=getint(),b=getint(),t=getint(); 29 c[b][a]=c[a][b]=t; 30 } 31 for(int k=1;k<=p;k++) { 32 for(int i=1;i<=p;i++) { 33 for(int j=1;j<=p;j++) { 34 c[i][j]=min(c[i][j],c[i][k]+c[k][j]); 35 } 36 } 37 } 38 int ans,mmin=inf; 39 for(int i=1;i<=p;i++) { 40 int tmp=0; 41 for(int j=0;j<F;j++) { 42 tmp+=c[i][f[j]]; 43 } 44 if(tmp<mmin) { 45 ans=i; 46 mmin=tmp; 47 } 48 } 49 printf("%d ",ans); 50 return 0; 51 }