解决此类问题首先是要读题目，本题有一个重点，在都满足的情况下选择离加油站最近的那个居民点的距离要尽量远。如果没有读题清楚可能这里会出错，另外注意本题的输出，最小的那个距离是double形式的，所以要么设置要同一。最后dev和cb两种开发环境下结果不同，如果在dev下的结果为3.2也不用慌，最后在在线提交上去的时候就是3.3了。
#include<cstdio> #include<string> #include<iostream> #include<vector> #include<cstring> using namespace std; const int maxn=10100; const int inf=0x3fffffff; int n,m,k,ds,d[maxn],G[maxn][maxn],ansid=0; double ansavg=inf,ansmin=-1; bool vis[maxn]={false}; int change(string a) { int len=a.size(),id=0; for(int i=0;i<len;i++) { if(a[i]!='G') { id=id*10+(a[i]-'0'); } } if(a[0]=='G') return n+id; else return id; } void dijkstra(int s) { fill(d,d+maxn,inf); memset(vis,false,maxn); d[s]=0; for(int i=1;i<=n+m;i++) { int min=inf,u=-1; for(int j=1;j<=n+m;j++) { if(vis[j]==false&&d[j]<min) { u=j; min=d[j]; } } if(u==-1)return; vis[u]=true; for(int v=1;v<=n+m;v++) { if(vis[v]==false&&G[u][v]!=inf&&G[u][v]+d[u]<d[v]) { d[v]=G[u][v]+d[u]; } } } } int main() { cin>>n>>m>>k>>ds; string str1,str2; int c1,c2,dis; fill(G[0],G[0]+maxn*maxn,inf); for(int i=0;i<k;i++) { cin>>str1>>str2>>dis; c1=change(str1); c2=change(str2); G[c1][c2]=G[c2][c1]=dis; } for(int i=n+1;i<=n+m;i++) { dijkstra(i); bool flag=false; double min=inf; double avg=0; for(int j=1;j<=n;j++) { if(d[j]>ds) { flag=true; break; } avg+=1.0*d[j]/n; if(d[j]<min) min=d[j]; } if(flag==true) continue; if(min>ansmin) { ansmin=min; ansid=i; ansavg=avg; } else if(min==ansmin&&avg<ansavg) { ansid=i; ansavg=avg; } } if(ansid!=0) { printf("G%d\n",ansid-n); printf("%.1f %.1f",ansmin,ansavg); } else { printf("No Solution"); } }