PAT L3-005

【Tip】

Dijsktra模板题

【Code】

#include<bits/stdc++.h>
#define fill(x) memset(x,0,sizeof(x))
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=30000;

int N,M,K,D;
char alpha1[100],alpha2[100];
int now,goal,di;
 
struct Edge{
    int from,to,dist;
};
struct HeapNode{  //Dijkstra算法用到的优先队列的节点
    int d,u;
    bool operator<(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};
struct Dijkstra{
    int n,m; //点数和边数
    vector<Edge> edges; //边列表
    vector<int> G[maxn]; //每个节点出发的边编号(从0开始编号)
    bool done[maxn];    //是否永久标号
    int d[maxn];        //s到各个点的距离
    int p[maxn];        //最短路中的上一条边

    void init(int n){
        this->n=n;
        for(int i=0;i<n;++i) G[i].clear();//清空邻接表
        edges.clear();//清空边表
    }
    
    void AddEdge(int from,int to,int dist){
        //如果是无向图,每条无向边需调用两次AddEdge
        edges.push_back((Edge){from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }
    
    void dijkstra(int s){//求s到所有点的距离
         priority_queue<HeapNode> Q;
         for(int i=0;i<n;++i) d[i]=INF;
         d[s]=0;
         fill(done);
         Q.push((HeapNode){0,s});
         while(!Q.empty()){
             HeapNode x=Q.top(); Q.pop();
            int u=x.u;
            if(done[u])continue;
            done[u]=true;
            for(int i=0;i<G[u].size();++i){
                Edge &e=edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
         }
    }
};
int main(){
    while(~scanf(“%d%d%d%d”,&N,&M,&K,&D)){
        Dijkstra dj;
        dj.init(N+M);
        for(int i=0;i<K;++i){
            scanf(“\n%s %s %d”,alpha1,alpha2,&di);
            //因为可能出现G10 123等字符串
            //所以这里转换必须用atoi或stoi
            //后者是c11的
            if(alpha1[0]==’G’){
                now = N-1 + atoi(alpha1+1);
            }else
                now = atoi(alpha1)-1;
                
            if(alpha2[0]==’G’){
                goal = N-1 + atoi(alpha2+1);
            }else
                goal = atoi(alpha2)-1;
            
            dj.AddEdge(now,goal,di);
            dj.AddEdge(goal,now,di);
        }
        int ansid=-1,ansdis=INF;
        double ansave=INF;
        
        for(int i=0;i<M;++i){
            int index=i+N,mindis=INF;
            bool flag=true;
            double ave=0.0;
            dj.dijkstra(index);
            for(int j=0;j<N;++j){
                if(dj.d[j]>D){
                    flag=false;
                    break;
                }
                ave+=1.0*dj.d[j];
                mindis=mindis>dj.d[j]?dj.d[j]:mindis;
            }
            if(!flag)
                continue;
            else{
                if(ansdis==INF){
                    ave=ave/N;
                    ansave=ave;
                    ansid=i;
                    ansdis=mindis;
                }else if(mindis>ansdis){
                    ave=ave/N;
                    ansave=ave;
                    ansid=i;
                    ansdis=mindis;
                }else if(ansdis==mindis){
                    ave=ave/N;
                    if(ave<ansave){
                        ansave=ave;
                        ansid=i;
                        ansdis=mindis;
                    }else if(ave==ansave){
                        ansid=i>ansid?ansid:i;
                        ansdis=mindis;
                    }
                }
            }
        }
        
        if(ansid==-1)
            printf(“No Solution\n”);
        else{
            printf(“G%d\n”,ansid+1);
            printf(“%.1f %.1f\n”,1.0*ansdis,ansave);
        }
    }
    return 0;
}