题解：P10951 最优高铁环

· · 题解

要做题,先读题

从题干中得到,此题为环尽然是环那就得遵循

//既可以使用栈来优化,也可以用玄学优化
//当松弛的次数 > 点数*2 的时候默认存在环

然后读题得到此题点数是5000

套公式

不过本题特殊特殊在它只能使用玄学优化

代码如下

#include<bits/stdc++.h>
#include<windows.h>
#include<algorithm>
#include<queue>
using namespace std;
const int N=5010,M=5e4+10;
int h[N],e[M],w[M],ne[M],idx;
int cnt[N],st[N];
double dist[N];
char car[200];
int q[N];
unordered_map<char,int> row={{'S',1},{'G',2},{'D',3},{'T',4},{'K',5}};
void add(int a,int b,int c){
    e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++;
}

int get(int x,int y){
    return (x-1)*1000+y;
}

int spfa(double x){
    memset(dist,0,sizeof dist);
    memset(cnt,0,sizeof cnt);

    //图不一定联通
    int head=0,tail=0;
    for(int i=1;i<=5000;++i) q[tail++]=i,st[i]=1;

    int count =0;
    while(q.size()){
        auto t=q[head++]();
        if(head==N) head=0;
        st[t]=0;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            double val=w[i]-x;

            if(dist[j]<dist[t]+val){
                dist[j]=dist[t]+val;
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=5000) return 1;

                if(++count> 10000) return 1; //玄学优化

                if(st[j]==0){
                    st[j]=1;
                    q[tail++]=j;
                    if(tail==N) tail=0;
                }
            }
        }
    }
    return 0;
}
int main(){
    memset(h,-1,sizeof h);
    int m;
    scanf("%d",&m);
    while(m--){
        scanf("%s",car);
        string sta,ed;
        for(int i=0;car[i]!='-';++i) sta+=car[i];
        int n=strlen(car);
        for(int i=n-1;car[i]!='-';--i) ed+=car[i];
        reverse(ed.begin(),ed.end());
        int w=0;

        for(int i=0;i<n;++i){
            if(car[i]=='S') w+=1000;
            else if(car[i]=='G') w+=500;
            else if(car[i]=='D') w+=300;
            else if(car[i]=='T') w+=200;
            else if(car[i]=='K') w+=150;
        }
        int x1=row[sta[0]],x2=row[ed[0]];
        int y1=0,y2=0;
        for(int i=1;i<sta.size();++i) y1=y1*10+(sta[i]-'0');
        for(int i=1;i<ed.size();++i) y2=y2*10+(ed[i]-'0');
        add(get(x1,y1),get(x2,y2),w);

    }

    if(spfa(0)==0) puts("-1");
    else{

        double l=0,r=2e4+10;
        while(r-l>1e-8){
            double mid=(l+r)/2;
            if(spfa(mid)) l=mid;
            else r=mid;
        }
        printf("%.0lf\n",r); //四舍五入
    }
    return 0;
}