最优高铁环

#include<bits/stdc++.h>
using namespace std;
typedef pair<double,int> PII;
vector <PII> G[50005];
double dis[50005];
short vis[50005];
int m,n;
map <string,int> M;
int spfa(int rt,double mid){
	vis[rt]=1;
	for(int i=0;i<G[rt].size();i++){
		int to=G[rt][i].second;
		double w=G[rt][i].first;
		if(dis[to]>dis[rt]+w-mid){
			dis[to]=dis[rt]+w-mid;
			if(vis[to]||spfa(to,mid)) return 1;
		}
	}
	vis[rt]=0;
	return 0;
}
int check(double mid){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f3f3f3f,sizeof(dis));
	for(int i=1;i<=n;i++){
		if(spfa(i,mid)) return 1;
	}
	return 0;
}
int main(){
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		char ch[150];
		scanf("%s",ch);
		int len=strlen(ch),js=-1;
		double sum=0;
		string be,en;
		for(int j=0;j<len;j++){
			if(ch[j]=='S') sum+=1000;
			else if(ch[j]=='G') sum+=500;
			else if(ch[j]=='D') sum+=300;
			else if(ch[j]=='T') sum+=200;
			else if(ch[j]=='K') sum+=150;
		}
		for(int j=0;j<len;j++){
			if(ch[j]=='-') break;
			be+=ch[j];
		}
		for(int j=len-1;j>=0;j--){
			if(ch[j]=='-'){
				js=j+1;
				break;
			}
		}
		for(int j=js;j<len;j++) en+=ch[j];
		if(!M[be]) M[be]=++n;
		if(!M[en]) M[en]=++n;
		G[M[be]].push_back({sum,M[en]});
	}
	double l=0,r=0x7fffffff,mid;
	while(r-l>=0.001){
		mid=(l+r)/2.0;
		if(check(mid)==0) l=mid;
		else r=mid;
	}
	if(l==0x7fffffff) printf("-1");
	else printf("%.0lf",l);
	return 0;
}