记录编号	586373	评测结果	AAAAAAAA
题目名称	[CH 6B12]最优高铁环	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.208 s
提交时间	2024-01-17 19:03:53	内存使用	8.12 MiB

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<queue>
#include<cmath>
#include<iomanip>
using namespace std;
const int maxm=50010;
string r;
map<string,int> xh;
int m,h[maxm],ne[maxm<<1],v[maxm<<1],tot=0,s=0,rl,rr,l,b[maxm],cnt[maxm];
double e[maxm<<1],ma=0,dis[maxm];
double cha(char p)
{
    switch(p)
    {
        case'S':
            return 1000;
            break;
        case'G':
            return 500;
            break;
        case'D':
            return 300;
            break;
        case'T':
            return 200;
            break;
        case'K':
            return 150;
            break;
        default:
            break;
    }
}

void q(int cl,int cr)
{
    //cout<<cl<<' '<<cr<<endl;
    if(cl!=0&&cr!=l-1)
    {
        return;
    }
    char a[10]={};
    int t=-1;
    for(int i=cl;i<=cr;i++)
    {
        t++;
        a[t]=r[i];
        //cout<<a[t]<<endl;
    }
    //cout<<a<<endl;
    if(xh[a]==0)
    {
        s++;
        xh[a]=s;
    }
    if(cl==0)
    {
        rl=xh[a];
        //cout<<'!'<<rl<<endl;
    }
    if(cr==l-1)
    {
        rr=xh[a];
        //cout<<'&'<<rr<<endl;
    }
}
void add(int x,int y,double z)
{
    tot++;
    e[tot]=z;
    v[tot]=y;
    ne[tot]=h[x];
    h[x]=tot;
}
int spfa(double mid)
{
    queue<int> q;
    for(int i=1;i<=s;i++)
    {
        q.push(i);
    }
    for(int i=0;i<50010;i++)
    {
        dis[i]=0;
    }
    memset(b,0,sizeof(b));
    memset(cnt,0,sizeof(cnt));
    int count=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        b[x]=0;
        for(int i=h[x];i;i=ne[i])
        {
            int y=v[i];
            //cout<<e[i]-mid<<endl;
            if(dis[y]<dis[x]+e[i]-mid)
            {
                dis[y]=dis[x]+e[i]-mid;
                cnt[y]=cnt[x]+1;
                if(cnt[y]>=s)
                {
                    return 1;
                }
                if(b[y]==0)
                {
                    b[y]=1;
                    q.push(y);
                }
            }
            count++;
            if(count>100000)
            {
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    freopen("highspeed.in","r",stdin);
    freopen("highspeed.out","w",stdout);
    scanf("%d",&m);
    string k;
    getline(cin,k);
    while(m--)
    {
        getline(cin,r);
        l=r.length();
        double z=0;
        int st=0,en;
        for(int i=0;i<l;i++)
        {
            if(r[i]>='A'&&r[i]<='Z')
            {
                z+=cha(r[i]);
            }
            if(r[i]=='-')
            {
                en=i-1;
                q(st,en);
                st=i+1;
            }
            if(i==l-1)
            {
                en=l-1;
                q(st,en);
            }
        }
        add(rl,rr,z);
        ma=max(ma,z);
        //cout<<rl<<' '<<rr<<' '<<z<<endl;
    }
    //cout<<ma<<endl;
    double q=0,z=ma;
    while(z-q>=0.01)
    {
        double mid=(z+q)/2.0;
        if(spfa(mid)==1)
        {
            q=mid;
        }
        else
        {
            z=mid;
        }
    }
    if(q==0)
    {
        cout<<"-1";
    }
    else
    {
        printf("%.0lf",q);
    }
    return 0;
}