C++(g++ 7.5.0) 解法, 执行用时: 54ms, 内存消耗: 2040K, 提交时间: 2022-08-21 10:37:02

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define il inline
#define co const
typedef long long ll;
co int N=5e4+1;
co double eps=1e-3;
int n,m,st,ed,t;
int head[N],edge[N],nt[N],tot;
double d[N],s[N],leng[N];
bool v[N];
 
il void add(int x,int y){
    edge[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
il int f(char ch){
    switch(ch){
        case 'S': t=0;return 1000;
        case 'G': t=1;return 500;
        case 'D': t=2;return 300;
        case 'T': t=3;return 200;
        case 'K': t=4;return 150;
    }
    return -1;
}
bool dfs(int x){
    v[x]=1;
    for(int i=head[x];i;i=nt[i]){
        int y=edge[i];double z=leng[i];
        if(d[y]>d[x]+z){
            d[y]=d[x]+z;
            if(v[y]||dfs(y)) return 1;
        }
    }
    v[x]=0;
    return 0;
}
bool pd(double x){
    for(int i=1;i<=m;++i) leng[i]=x-s[i];
    memset(v,0,sizeof v);
    memset(d,0x3f,sizeof d);
    for(int i=1;i<N;++i)
        if(dfs(i)) return 1;
    return 0;
}
int main(){
    cin>>m;
    for(int i=1;i<=m;++i){
        static char str[150];
        scanf("%s",str),n=strlen(str);
        int x=0;
        bool flag=0;
        for(int j=0;j<n;++j){
            if(isdigit(str[j])) x=x*10+str[j]-'0';
            else if(str[j]=='-'){
                if(!flag) st=x+t*10000;
                flag=1;
                x=0;
            }
            else s[i]+=f(str[j]);
        }
        ed=x+t*10000;
        add(st,ed);
    }
    double l=0,r=0x7fffffff,ans=-1;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(pd(mid)) l=ans=mid;
        else r=mid;
    }
    printf("%.0lf\n",ans);
    return 0;
}

C++ 解法, 执行用时: 104ms, 内存消耗: 2484K, 提交时间: 2021-09-01 16:05:51

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+90;
const double eps=1e-3;

int n;
map<string,int> M;
int cnt;
int cnte,ver[N],nxt[N],head[N];
double l,r;
int we[N];
double dis[N],edge[N];

int get_point(string a){
	if(M.find(a)!=M.end()) return M[a];
	return M[a]=++cnt;
}

int f(char ch){
	switch (ch)
	{
		case 'S': return 1000;
		case 'G': return 500;
		case 'D': return 300;
		case 'T': return 200;
		default : return 150;
	}
	return -1;
}

void add(int a,int b,double c){
	nxt[++cnte]=head[a],head[a]=cnte,ver[cnte]=b,edge[cnte]=c;
}

void read(string a){
	int len=a.size();
	int i=0,fl=0,x=0,y=0;double v=0;
	while(i<len)
	{
		string temp="";
		while(i<len&&a[i]!='-') temp+=a[i++];
		i++;
		if(!fl) x=y=get_point(temp);
		fl=1;
		if(i==len+1) y=get_point(temp);
		v+=f(temp[0]);
	}
	add(x,y,v);
	r+=v;
}

bool dfs(int i,double mid){
	we[i]=1;
	for(int io=head[i];io;io=nxt[io])
	{
		int v=ver[io];
		if(dis[v]>dis[i]+mid-edge[io])
		{
			dis[v]=dis[i]+mid-edge[io];
			if(we[v]||dfs(v,mid)) return true;
		}
	}
	we[i]=0;
	return false;
}

bool check(double mid){
	memset(we,0,sizeof we);
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=cnt;i++)
		if(dfs(i,mid)) return true;
	return false;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		string a;
		cin>>a;
		read(a);
	}
	double as=-1;
	while(l+eps<r)
	{
		double mid=(l+r)/2;
		if(check(mid)) l=as=mid;
		else r=mid;
	}
	printf("%.0lf",as);
	
	return 0;
}