1072. Gas Station (30) Dijkstra算法求所有居住点到候选gas staion的最短距离，如果其中某个点最短距离大于ds则超出范围；注意题目中gas点和居住点的区别，本代码将gas点放于1000后
#include <iostream>#include <vector>#include <cstdio>#include <algorithm>using namespace std;const int INF=999999999,Max=1020;int a[Max][Max];struct node{ int gasv; double avg; double min;};bool comp(const node &a,const node &b){ if(a.avg!=b.avg) return a.avg<b.avg; return a.gasv<b.gasv;}void InitMatrix(void){ for(int i=1;i<Max;++i) { for(int j=1;j<Max;++j) { if(i==j)a[i][j]=0; else a[i][j]=INF; } }}int TransStringToInteger(string &s){ if(s[0]=='G') { s=s.substr(1); return atoi(s.c_str())+1000; } return atoi(s.c_str());}bool isResidentialHouse(int u){ return (u<=1000)?true:false;}int main(){ int n,m,arcnum,ds; vector<node> ans; InitMatrix(); cin>>n>>m>>arcnum>>ds; for(int i=0;i<arcnum;++i) { string s1,s2; int dis; cin>>s1>>s2>>dis; int u=TransStringToInteger(s1),v=TransStringToInteger(s2); a[u][v]=dis; a[v][u]=dis; } int PRemin=-1; for(int gv=1;gv<=m;++gv) { int v=gv+1000; int dist[Max]={0},visit[Max]={0}; for(int i=1;i<Max;++i) dist[i]=a[i][v]; visit[v]=1; int u; for(int i=1;i<Max;++i) { int min=INF; for(int j=1;j<Max;++j) { if(!visit[j]&&dist[j]<min) { min=dist[j]; u=j; } } visit[u]=1; for(int k=1;k<Max;++k) { if(a[k][u]<INF&&dist[k]>dist[u]+a[u][k]) dist[k]=dist[u]+a[u][k]; } } bool isrange=true; int mindis=INF; double sumdis=0.0; for(int w=1;w<=n;++w) { sumdis+=dist[w]; if(mindis>dist[w]&&dist[w]!=0)mindis=dist[w]; if(dist[w]>ds){isrange=false;break;} } if(isrange) { node temp; temp.gasv=v; temp.avg=sumdis/n; temp.min=mindis; if(premin<mindis) { ans.clear(); ans.push_back(temp); premin=mindis; } else if(premin==mindis) ans.push_back(temp); } } sort(ans.begin(),ans.end(),comp); if(!ans.size()) cout<<"No Solution"; else { string s="G"; cout<<s<<ans[0].gasv%1000<<endl; printf("%.1lf %.1lf",ans[0].min,ans[0].avg+0.0000001); } return 0;}新闻热点
疑难解答
