PAT1072 Gas Station-Dijkstra算法

原题链接

1072 Gas Station

思路

题目大意,存在n个居民点和m个加油站。现在需要从这m个加油站中选出一个加油站,要求这个加油站到所有居民点中最短距离的最短距离要最大,且距离不能超过输入中指定的范围。
需要注意的是,计算最短距离时,需要考虑居民点和加油站,因为加油站和居民点之间也是有路径可达的。
为了表示的方便,将加油站的编号变换到n+1~n+m之间。我想这一步对你而言应该很简答。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,k,range; 
const int inf = 0x3f3f3f;
int graph[1020][1020];//居民点和加油站 
int dis[1020],ans[1020];//存放最大距离和最终结果 
int ansid = -1;
double ansmin = -1,ansave = inf;
void dijkstra(int s){
    //得到所有居民点到s点的最短距离。可以通过其它加油站进行中转??
    fill(dis,dis+1020,inf);
    bool visited[1020];
    fill(visited,visited+1020,false);
    dis[s] = 0; 
    bool isok = true;
    double tmpmin = inf;
    double tmpsum = 0;//记录该情况下的最大距离 
//  cout<<"s="<<s<<endl;
    for(int i=1;i<=n+m;i++){
        int u = -1,mind = inf;//最小的下标和对应的值
        for(int j = 1;j<=n+m;j++){
            if(!visited[j] && dis[j] < mind){
                u = j;
                mind = dis[j];
            }
        }
        if(u == -1)break;//已经找不到了 
        visited[u] = true;
        if(u <= n){
            tmpsum += mind;
        }
        if(u<=n && mind > range){//超出服务范围 
            isok = false;
            break;
        }else if (u<=n && mind < tmpmin){
            tmpmin = mind;
        }
        for(int k = 1;k <= n+m;k++){
            if(!visited[k] && dis[u]+graph[u][k] < dis[k]){
                dis[k] = dis[u]+graph[u][k];
            }
        } 
    }   
    if(isok){
        tmpsum /= (1.0*n);
        if(tmpmin > ansmin){ //最小距离尽可能的大 
            ansid = s; 
            ansmin = tmpmin; //距离更小。更新
            ansave = tmpsum;
        }else if(tmpmin == ansmin){//最小距离相等是,取平均值更小的 
            if(tmpsum < ansave){
                ansid = s;
                ansmin = tmpmin;
                ansave = tmpsum;
            }
        }
    }
} 

int main(){
    //该点到任意居民点的最短距离要尽可能的大
    //但必须在服务范围内
    //有重复的输出平均最短距离小的
    //输入序号小的
    for(int i =0;i<=1020;i++){
        for(int j=0;j<1020;j++){
            graph[i][j] = inf;
        }
    }
    scanf("%d%d%d%d",&n,&m,&k,&range);
    //1-n为居民点,n+1~n+m是加油站
    for(int i=0;i<k;i++){
        string a,b;
        int ta=0,tb=0,dis;
        cin>>a>>b>>dis;
        if(a[0]=='G') ta = n + stoi(a.substr(1));
        else ta = stoi(a);
        if(b[0]=='G') tb = n + stoi(b.substr(1));
        else tb = stoi(b);      
        graph[ta][tb] = graph[tb][ta] = min(graph[ta][tb],dis);//防止重边 
    } 
    for(int i=n+1;i<=n+m;i++){
        dijkstra(i);
    }
    if(ansid == -1){
        printf("No Solution\n");
    }else{
        string id = "G"+to_string(ansid-n) ;
        cout<<id<<endl;
        printf("%0.1f %0.1f\n",ansmin,ansave);
    }
    return 0;
} 

Add a Comment

邮箱地址不会被公开。