Gas Station (30)

#pragma warning (disable:4996)
#include <iostream>
#include <cstdlib>
#include <limits.h>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 1009
int N, M, K; double Ds;
int d[MAX][MAX];

int res_id;
double max_min_d = 0, min_aver_d = INT_MAX;

int p_id(char* x) {
    if (x[0] == 'G')return atoi(x + 1) + N;
    else return atoi(x);
}

int main()
{
    cin >> N >> M >> K >> Ds;
    for (int i = 1; i <= N + M; ++i)
        for (int j = 0; j <= N + M; ++j)
            d[i][j] = INT_MAX / 2;
        
    for (int i = 1; i <= N + M; ++i) d[i][i] = 0;
    
    for (int i = 0; i < K; ++i) {
        char p1[100], p2[100]; int tmp;
        cin >> p1 >> p2 >> tmp;
        int n1 = p_id(p1), n2 = p_id(p2);
        d[n1][n2] = min(d[n1][n2], tmp);//专门处理起点-终点间有多条边的情况(包括自环)
        d[n2][n1] = d[n1][n2];
    }

    //Floyd
    for (int k = 1; k <= N + M; ++k)
        for (int i = 1; i <= N + M; ++i)
            for (int j = 1; j <= N + M; ++j)
                if (d[i][j] > d[i][k] + d[k][j])
                    d[i][j] = d[i][k] + d[k][j];


    bool isFind = false;
    for (int gi = N + 1; gi <= N + M; ++gi) {
        bool G_OK = true;
        int tmp_sum = 0.0;
        int min_d = INT_MAX;
        for (int i = 1; i <= N; ++i) {
            if (d[gi][i] > Ds) {
                G_OK = false; break;
            }
            tmp_sum += d[gi][i];
            if (min_d > d[gi][i])//注意！要保证min_d一开始一定要大于d,两者初始化分别为INT_MAX和INT_MAX/2
                min_d = d[gi][i];
        }
        if (!G_OK)continue;

        if (max_min_d <= min_d) {
            if (max_min_d < min_d) {
                max_min_d = min_d;
                isFind = true; res_id = gi - N;
                min_aver_d = tmp_sum * 1.0 / N;
            }
            else if (min_aver_d > tmp_sum * 1.0 / N) {
                isFind = true; res_id = gi - N;
                min_aver_d = tmp_sum * 1.0 / N;
            }
        }
    }

    if (isFind) {
        cout << 'G' << res_id << endl;
        printf("%.1f %.1f", max_min_d, min_aver_d);
    }
    else cout << "No Solution";
    return 0;
}

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;
int N, M, K;
float Ds;

vector<pair<int, float>> edges[10005];
int main() {
    scanf("%d %d %d %f", &N, &M, &K, &Ds);
    for(int i = 0 ; i < K; i ++)
    {
        char u[6], v[6];
        float w;
        scanf("%s", &u);
        scanf("%s",&v);
        scanf("%f",&w);
        int uIdx, vIdx;
        uIdx = (u[0] == 'G') ? N + atoi(u+1) : atoi(u);
        vIdx = (v[0] == 'G') ? N + atoi(v+1) : atoi(v);

        edges[uIdx].push_back({vIdx, w});
        edges[vIdx].push_back({uIdx, w});
    }

    float resultMinDist = -1, resultAvgDist = 0.0;
    int resultIdx = N+1;

    for(int i = N + 1; i <= N + M; i ++)
    {
        priority_queue<pair<float, int>> que; // minDist, idx
        vector<float> minDist(N+M+1, -1);
        //vector<bool> visited(N+M+1, false);
        int rootIdx = i;
        minDist[rootIdx] = 0;
        que.push({minDist[rootIdx], rootIdx});
        while( !que.empty())
        {
            auto a = que.top();
            int idx = a.second;
            que.pop();
            for(pair<int, float> e : edges[idx])
            {
                int adjIdx = e.first;
                float w = e.second;
                if (minDist[adjIdx] < 0 || minDist[adjIdx] > w + minDist[idx])
                {
                    minDist[adjIdx] = w + minDist[idx];
                    que.push({minDist[adjIdx], adjIdx});
                }
            }
        }
        // summary
        float minServeDist = -1, avgServeDist = 0.0;
        bool failFlag = false;
        for(int j = 1; j <= N; j++)
        {
            if(minDist[j] > Ds)
            {
                failFlag = true;
                break; // fail
            }
            else
            {
                if(minServeDist < 0)
                    minServeDist = minDist[j];
                else
                    minServeDist = min(minServeDist, minDist[j]);

                avgServeDist += minDist[j];
            }
        }
        if(!failFlag)
        {
            avgServeDist /= N;
            if (resultMinDist < 0 || resultMinDist < minServeDist ||
                (resultMinDist == minServeDist && avgServeDist < resultAvgDist))
            {
                resultMinDist = minServeDist;
                resultAvgDist = avgServeDist;
                resultIdx = i;
            }
        }

    }
    if(resultMinDist > 0) {
        printf("G%d\n", resultIdx - N);
        printf("%.1f %.1f", resultMinDist, resultAvgDist);
    }
    else
        printf("No Solution");
    return 0;
}

#include <bits/stdc++.h>
(755)#define min(a,b) ((a)<(b)? (a):(b))
#define INF 99999999
using namespace std;
struct Road{
	int target;
	int distant;
};
int hourseNum, gasNum, roaseNum, serverDis;

//将用字符串表示的节点下标转换成整数下标
int translate(string nodeName){
	if (nodeName[0] != 'G') return atoi(nodeName.c_str());
	return hourseNum + atoi(nodeName.substr(1).c_str());
}
//答案组合
struct Result{
	int id;
	int totalDis;
	int min;
	bool operator < (const Result &b) const{
		if (min != b.min) return min > b.min;
		if (totalDis != b.totalDis) return totalDis < b.totalDis;
		return id < b.id;
	}
};
vector<Result>ansQue;
vector< vector<Road> >nodes;	//从1开始

int main(){
	//获取数据输入
	scanf("%d %d %d %d", &hourseNum, &gasNum, &roaseNum, &serverDis);
	nodes.resize(hourseNum + gasNum + 1);
	for (int i = 0; i < roaseNum; i++){
		string from, to;
		int distant;
		cin >> from >> to >> distant;
		nodes[translate(from)].push_back({ translate(to), distant });
		nodes[translate(to)].push_back({ translate(from), distant });
	}
	//对所有的油站计算最短路
	int ansIndex=-1, ansMin=INF;
	double ansAvg=0.0;
	for (int id = hourseNum + 1; id <= hourseNum + gasNum; id++) {
		vector<bool> visit(hourseNum + gasNum + 1, false);
		vector<int> distant(hourseNum + gasNum + 1, INF);	//从油站id到个个节点的距离
		//初始化数据
		distant[id] = 0;
		visit[id] = true;
		for (auto i = nodes[id].begin(); i < nodes[id].end(); i++){
			distant[i->target] = min(distant[i->target], i->distant);
		}
		//寻找以id为起点的最短路
		for (int i = 0; i < hourseNum + gasNum; i++){
			int shortest = INF, next=-1;
			//收纳最近节点
			for (int j = 1; j <= hourseNum+gasNum; j++){
				if (!visit[j] && distant[j] < shortest){
					next = j;
					shortest = distant[j];
				}
			}
			if (shortest > serverDis || next<0) break;	//虽然可以连通，但是距离超出范围
			visit[next] = true;
			//更新其他节点的最短路径
			for (auto j = nodes[next].begin(); j < nodes[next].end(); j++){
				if (distant[next] + j->distant < distant[j->target]){
					distant[j->target] = distant[next] + j->distant;
				}
			}
		}
		//分析结果并更新答案
		bool can = true;
		int totalDis = 0, minDis = INF;
		for (int i = 1; i <= hourseNum; i++){
			if (i == id) continue;
			if ( distant[i] > serverDis) {	//服务距离仅筛选住宅
				can = false;
				break;
			}
			minDis = min(minDis, distant[i]);
			totalDis += distant[i];
		}
		if (can){
			ansQue.push_back({id-hourseNum, totalDis, minDis});
		}
	}
	//输出答案
	if (ansQue.empty()){
		cout << "No Solution" << endl;
	}
	else{
		sort(ansQue.begin(), ansQue.end());
		Result ans = ansQue[0];
		printf("G%d\n%.1f %.1f\n", ans.id, double(ans.min), double(ans.totalDis) / hourseNum);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+20;
const int INF=0x3f3f3f3f;
int n,m,k,Ds,G[maxn][maxn],dis[maxn];//1~n:house n+1~n+m:station
bool visit[maxn];

int getId(string &s){
    if(s[0]=='G'){
        if(s.size()==2) return n+s[1]-'0';
        else return n+10;
    }else{
        return stoi(s);
    }
}
//最短路径
void dijkstra(int s,int N){
    fill(dis,dis+N+1,INF);
    fill(visit,visit+N+1,0);
    dis[s]=0;
    for(int i=1;i<=N;i++){
        int u=-1,min=INF;
        for(int j=1;j<=N;j++){
            if(!visit[j] && dis[j]<min){
                min=dis[j];
                u=j;
            }
        }
        if(u==-1) return;
        visit[u]=true;
        for(int v=1;v<=N;v++){
            if(!visit[v] && G[u][v]!=0){
                int tempDis=dis[u]+G[u][v];
                if(tempDis<dis[v]){
                    dis[v]=tempDis;
                }
            }
        }
    }
}
int main()
{   
    fill(G[0],G[0]+maxn*maxn,INF);
    cin>>n>>m>>k>>Ds;
    string p1,p2;
    int a,b,c;
    for(int i=0;i<k;i++){
        cin>>p1>>p2>>c;
        a=getId(p1);
        b=getId(p2);
        G[a][b]=G[b][a]=min(c,G[a][b]);
    }
    int choice=-1;
    double minDis=-INF,meanDis,tempMindis,tempMeandis;
    for(int i=n+1;i<=n+m;i++){
        dijkstra(i,n+m);
        if(*max_element(dis+1,dis+n+1)>Ds) continue;//存在dis>Ds
        tempMindis=*min_element(dis+1,dis+n+1);
        tempMeandis=accumulate(dis+1,dis+n+1,0)*1.0/n;
        //比较不同出发点，house到station的最短距离
        if(tempMindis>minDis){
            minDis=tempMindis;
            meanDis=tempMeandis;
            choice=i-n;
        }else if(tempMindis==minDis){
            if(tempMeandis<meanDis){
                meanDis=tempMeandis;
                choice=i-n;                
            }
        }
    }
    if(choice!=-1){
        cout<<"G"<<choice<<endl;
        printf("%.1f %.1f",minDis,meanDis);
    }else{
        cout<<"No Solution";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m,k,l;
#define inf 999999
int a[1200][1200];
int dis[1200][1200];
void dj(int index1){
    int i,j;
    int book[n+m+1];
    memset(book,0,sizeof(book));
    fill(dis[index1],dis[index1]+n+m+1,inf);
    dis[index1][index1]=0;
    for(i=1;i<n+m+1;i++){
        int mn=inf,u=-1;
        for(j=1;j<n+m+1;j++){
            if(book[j]==0&&mn>dis[index1][j]){
                mn=dis[index1][j];
                u=j;
            }
        }
        if(u==-1)break;
        dis[index1][u]=mn;
        book[u]=1;
        for(j=1;j<n+m+1;j++){
            if(dis[index1][u]+a[u][j]<dis[index1][j]){
                dis[index1][j]=dis[index1][u]+a[u][j];
            }
        }
    }
    return ;
}
int convert(char a[]){
    int i;
    int k=0;
    if(a[0]=='G'){
        for(i=1;a[i]!='\0';i++){
           k=k*10+a[i]-'0'; 
        }
        k+=n;        
    }
    else {
        for(i=0;a[i]!='\0';i++){
            k=k*10+a[i]-'0';
        }
    }
    return k;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&k,&l);
    int i;
    int j;
    fill(a[0],a[0]+(1010)*(1010),inf);
    for(i=0;i<k;i++){
        char c[5];
        char b[5];
        scanf("%s%s",c,b);
        int s=convert(c);
        int t=convert(b);
        int dis;
        scanf("%d",&dis);
        a[s][t]=min(a[s][t],dis);
        a[t][s]=min(a[s][t],dis);
    }
    int c[n+m+1];
    fill(c,c+n+m+1,inf);
    int sum[n+m+1];
    memset(sum,0,sizeof(sum));
    int ans,ans1,ans2;
    ans=-1;
    ans1=INT_MIN;
    ans2=INT_MAX;
    for(i=n+1;i<n+m+1;i++){
        dj(i);
        for(j=1;j<=n;j++){
            sum[i]+=dis[i][j];
            if(c[i]>dis[i][j])c[i]=dis[i][j];
            if(dis[i][j]>l)break;
        }
        if(j==n+1){
            if(c[i]>ans1){
                ans=i-n;
                ans1=c[i];
                ans2=sum[i];
            }
            else if(c[i]==ans1&&sum[i]<ans2){
                ans=i-n;
                ans2=sum[i];
            }
        }
    }
    if(ans==-1){
        printf("No Solution\n");
    }
    else {
        printf("G%d\n",ans);
        printf("%.1lf %.1lf",(double)ans1,(double)ans2/n);
    }
    system("pause");
}

#include <iostream>
#include<map>
#include<vector>
#include<set>
#include<sstream>
#define INF 0x3fffffff
using namespace std;
struct Path
{
	int end;
	int dist;
	Path(int end, int dist) :end(end), dist(dist) {}
};

int maxDistOil = 0;
double minAverageDist = INF;
int index = -1;


void Dijstra(int start, int houses, int maxArange, int points, vector<Path>* graph) {
	bool* visited = new bool[points];
	int* pathLength = new int[points];
	int* pre = new int[points];
	for (int i = 0; i < points; i++)
	{
		visited[i] = false;
		pathLength[i] = INF;
		pre[i] = -1;
	}
	visited[start] = true;

	vector<Path> startPaths = graph[start];
	for (auto c : startPaths)
	{
		if (c.dist< pathLength[c.end])
		{
			pathLength[c.end] = c.dist;
		}
		pre[c.end] = start;
	}
	bool hasUnvisited = true;
	while (hasUnvisited)
	{
		int nextNode = -1, minLength = INF;
		hasUnvisited = false;
		for (int i = 1; i < points; i++)
		{
			if (visited[i] == false && pathLength[i] < minLength) {
				hasUnvisited = true;
				minLength = pathLength[i];
				nextNode = i;
			}
		}
		if (nextNode == -1) break;
		vector<Path> aimPath = graph[nextNode];
		visited[nextNode] = true;
		for (auto c : aimPath)
		{
			if (visited[c.end])
			{
				continue;
			}
			if (pathLength[nextNode] + c.dist < pathLength[c.end])
			{
				pathLength[c.end] = pathLength[nextNode] + c.dist;
				pre[c.end] = nextNode;
			}

		}

	}
	
	/*for (int i = 1; i < points; i++)
	{
		cout << i << " :" << pre[i] << endl;
	}
	cout << endl;
	for (int i = 1; i < points; i++)
	{
		cout << i << " :" << pathLength[i] << endl;
	}
	cout << endl;*/
	int maxDist = 0;
	int minDist = INF;
	int totalLength = 0;
	for (int i = 1; i <= houses; i++)
	{
		if (pathLength[i] > maxArange)
		{
			int index = -1;
			return;
		}
		totalLength += pathLength[i];
		if (pathLength[i] < minDist)
		{
			minDist = pathLength[i];
		}
	}
	if (maxDistOil < minDist)
	{
		maxDistOil = minDist;
		index = start;
		minAverageDist = totalLength;
	}
	else if (maxDistOil == minDist)
	{
		if (minAverageDist > totalLength) {
			// 如果平均距离更小，用这个新的index
			minAverageDist = totalLength;
			index = start;
		}
		else if (minAverageDist == totalLength) {
			if (index > start)
			{
				// 平均距离也相等，这个时候用小的id
				index = start;
			}
		}
	}


}

int main()
{
	ios::sync_with_stdio(false);
	int houses, candidates, paths, maxServiceRange;
	cin >> houses >> candidates >> paths >> maxServiceRange;
	map<string, int> candiToId;
	string name, end;
	int dist;
	int candiId = houses + 1;
	set<string> candidateNames;
	vector<Path>* graph = new vector<Path>[houses + candidates + 1];
	for (int i = 0; i < paths; i++)
	{
		cin >> name >> end >> dist;
		if (name.find("G") != -1 && candidateNames.find(name) == candidateNames.end())
		{
			candidateNames.insert(name);
			candiToId[name] = candiId;
			candiId++;
		}
		if (end.find("G") != -1 && candidateNames.find(end) == candidateNames.end())
		{
			candidateNames.insert(end);
			candiToId[end] = candiId;
			candiId++;
		}
		int startP = 0, endP = 0;
		if (candiToId.find(name) != candiToId.end())
		{

			startP = (*candiToId.find(name)).second;
		}
		else {
			startP = atoi(name.c_str());
		}
		if (candiToId.find(end) != candiToId.end()) {
			endP = (*candiToId.find(end)).second;
		}
		else {
			endP = atoi(end.c_str());
		}
		graph[startP].push_back(Path(endP, dist));
		graph[endP].push_back(Path(startP, dist));
	}

	/*
	for (auto i : candidateNames)
	{
		cout << i << " ";
	}
	for (int i = 1; i < houses+candidates+1; i++)
	{
		cout << endl;
		cout << i << ": ";
		for (auto c : graph[i]) {
			cout << c.end << " " ;
		}
	}
	cout << endl;*/
	for (auto c : candidateNames)
	{
		int startId = (*candiToId.find(c)).second;
		Dijstra(startId, houses, maxServiceRange, houses + candidates + 1, graph);
	}

	if (index == -1)
	{
		cout << "No Solution";
	}
	else {
		for (auto c : candidateNames)
		{
			int startId = (*candiToId.find(c)).second;
			if (startId == index)
			{
				cout << c << endl;
				break;
			}
		}

		printf("%d.0 %.1f", maxDistOil, minAverageDist/houses);
	}


}

/*
问题：得到多个点到其他顶点的最短路径矩阵，求其最小值和平均值，并按照最小值降序和平均值升序排列。输出第一个顶点的序号、最小值和平均值。
特殊要求：输入含字符串，需要进行判断和转换；输入要求保留1位小数，需要对结果进行转换。
解法：
*/
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAXSIZE 100000000				//距离上限，dist数组初始值

typedef struct MGnode* MGraph;		//邻接矩阵结构
struct MGnode {
	int vN, eN;
	int V[1020][1020];
};
MGraph G=new MGnode;							//全局变量
int N, M, K, D;
int visited[1020], dist[1020];
int charToInt(char* s) {
	if (s[0] == 'G') return atoi(s + 1);
	else return atoi(s) + M;
}
void Insert(int v1, int v2, int w) {
	if (w < G->V[v1][v2]) G->V[v1][v2] = G->V[v2][v1] = w;
}
void Build(int n, int m,int k) {		//输入转化为无向图
	G->vN = n+m; G->eN = k;
	//G->V = new int*[m+n+1];
	for (int i = 1; i < G->vN+1; i++) {
		//G->V[i] = new int[m+n+1];
		for (int j = 1; j < G->vN + 1; j++) {
			G->V[i][j] = MAXSIZE;
		}
	}
	int v1, v2, w;
	char c1[5], c2[5];
	for (int i = 1; i < k + 1; i++) {
		cin >> c1;
		v1 = charToInt(c1);
		cin >> c2;
		v2 = charToInt(c2);
		cin >> w;
		Insert( v1, v2, w);
	};
}
int FindNextNode() {				//找到dist数组中未标记的最短距离顶点
	int min = MAXSIZE, next=-1;
	for (int i = 1; i < G->vN+1; i++) {
		if (visited[i] == 0 && min > dist[i]) {
			next = i;
			min = dist[i];
		}
	}
	return next;
}
void FindMinDist(int v) {	//核心算法：修改后的dijistra算法
	for (int i = 1; i < N + M + 1; i++) {		//外部数组初始化，非常重要！！！
		dist[i] = MAXSIZE; visited[i] = 0;
	}
	int v1 = v;				//v1用于遍历
	dist[v1] = 0; 
	while (v1 != -1) {				//开始循环，FindNextNode返回-1表示已无未标记可抵达节点，即当前连通分量已遍历完毕
		visited[v1] = 1;
		for(int i=1;i<G->vN+1;i++)					//遍历当前节点的全部邻接点，选择未标记顶点进行操作
		{					
			if ( G->V[v1][i]!=MAXSIZE&&visited[i]==0&& dist[i] > dist[v1] + G->V[v1][i]) {	//发现更短路径，更新dist、path、team、pathcount数组
				dist[i] = dist[v1] + G->V[v1][i];
			}													
		}
		v1 = FindNextNode();												//前往下一个未标记顶点，对应大循环
		
	}
}
void PrintFloat(float f) {
	cout<<fixed<<setprecision(1)<< f;
}
int main() {
	cin >> N>>M>>K>>D;
	Build(N, M, K);					//建立图				
	int maxmindist = 0, flag = 0, idealnode = 0;
	float avedist = 0, t = 0;
	for (int i = 1; i < M + 1; i++) {
		flag = 0;
		FindMinDist(i);			//执行最短路径算法
		int mindist = MAXSIZE, totaldist = 0;
		for (int i = M + 1; i < M + N + 1; i++) {
			if (dist[i] > D)
			{
				flag = 1;
				break;
			}
			totaldist += dist[i];
			if (dist[i] < mindist) mindist = dist[i];
		}
		if (flag == 1) continue;
		t = 1.0*totaldist / N;
		if (maxmindist < mindist) {
			maxmindist = mindist;
			avedist = t;
			idealnode = i;
		}
		else if (maxmindist == mindist && t < avedist) {
			avedist = t;
			idealnode = i;
		}
	}
	if (idealnode == 0) cout << "No Solution";
	else {
		cout << 'G' << idealnode << endl;
		PrintFloat(float(maxmindist));
		cout << " ";
		PrintFloat(avedist);
	}
	return 0;
}

from math import inf
from sys import stdin
from statistics import mean


resident, gas, road, range_max = map(int, input().split())
spot = resident + gas
graph = [ [inf] * (spot+1) for _ in range(spot+1) ]
result, far_max, avg_min = 0, -inf, 0

for line in stdin.readlines():
    v1, v2, length = line.split()
    length = int(length)
    v1 = int(v1[1:]) + resident if v1[0] == 'G' else int(v1)
    v2 = int(v2[1:]) + resident if v2[0] == 'G' else int(v2)
    if v1 == v2: length = 0
    if graph[v1][v2] != inf:
        length = min(length, graph[v1][v2])
    graph[v1][v2] = graph[v2][v1] = int(length)

def Dijkstra(source):
    dist, collected = [inf] * (spot+1), [False] * (spot+1)
    dist[source] = 0
    while True:
        v, dist_min = -1, inf
        for i in range(1, spot+1):
            if not collected[i] and dist[i] < dist_min:
                v = i
                dist_min = dist[i]
        if v == -1: break
        collected[v] = True

        for w in range(1, spot+1):
            if graph[v][w] != inf and not collected[w]:
                if dist[v] + graph[v][w] < dist[w]:
                    dist[w] = dist[v] + graph[v][w]
    return dist

for i in range(resident+1, spot+1):
    dist = Dijkstra(i)
    dist_min = inf
    for r in range(1, resident+1):
        if dist[r] > range_max:
            dist_min = -1
            break
        if dist[r] < dist_min:
            dist_min = dist[r]
    if dist_min == -1: continue
    dist_avg = mean( dist[1:resident+1] )
    if dist_min > far_max or (dist_min == far_max and dist_avg < avg_min):
        result = i - resident
        far_max = dist_min
        avg_min = dist_avg

if result:
    print('G{}\n{:.1f} {:.1f}'.format( result, far_max, avg_min ))
else:
    print('No Solution')

#include<iostream>
(720)#include<vector>
#include<string>
(765)#include<queue>
#include<limits.h>
(1124)#include<float.h>
using namespace std;
const int MAXN = 1011;
typedef pair<int, int> PP;
struct Edge {
	int to;
	int length;
	Edge(int to, int n) :to(to), length(n) {}
};
int N, M, K, DS, x;
vector<Edge>graph[MAXN];
int dist[MAXN];
double mmin = DBL_MIN;
int index = 11;
double aver = DBL_MAX;
void dijkstra(int source) {
	priority_queue<PP, vector<PP>,greater<PP> >myqueue;
	fill(dist, dist + MAXN, INT_MAX);
	dist[source] = 0;
	myqueue.push(PP(0, source));
	while (!myqueue.empty()) {
		int u = myqueue.top().second;
		myqueue.pop();
		for (int i = 0; i < graph[u].size(); i++) {
			int v = graph[u][i].to;
			int length = graph[u][i].length;
			if (dist[v] > dist[u] + length) {
				dist[v] = dist[u] + length;
				myqueue.push(PP(dist[v], v));//pair先比较first，因此把距离放在first
			}
		}
	}
	int tmp_index = source, sum = 0;
	double tmp_aver, tmp_min = DBL_MAX ;
	for (int i = M + 1; i <= N + M; i++) {
		sum += dist[i];
		if (dist[i] > DS) {
			return;
		}
		else if (dist[i] < tmp_min) {
			tmp_min = dist[i];
		}
	}
	tmp_aver = sum * 1.0 / N;
	if (tmp_min > mmin) {
		mmin = tmp_min;
		index = tmp_index;
		aver = tmp_aver;
	}
	else if (tmp_min == mmin && tmp_aver < aver) {
		mmin = tmp_min;
		index = tmp_index;
		aver = tmp_aver;
	}
	else if (tmp_min == mmin && tmp_aver == aver && tmp_index < index) {
		mmin = tmp_min;
		index = tmp_index;
		aver = tmp_aver;
	}
}
int main() {
	string s1, s2;
	cin >> N >> M >> K >> DS;
	for (int i = 0; i < K; i++) {
		int u, v;
		cin >> s1;
		cin >> s2;
		if (s1[0] == 'G') {
			s1.erase(0, 1);
			u = stoi(s1, 0, 10);
		}
		else {
			u = stoi(s1, 0, 10) + M;
		}
		if (s2[0] == 'G') {
			s2.erase(0, 1);
			v = stoi(s2, 0, 10);
		}
		else {
			v = stoi(s2, 0, 10) + M;
		}
		cin >> x;
		graph[u].push_back(Edge(v, x));
		graph[v].push_back(Edge(u, x));
	}
	for (int i = 1; i <= M; i++) {
		dijkstra(i);
	}
	if (index!=11) {
		cout << "G" << index << '\n';
		printf("%.1lf %.1lf", mmin, aver);
	}
	else {
		printf("No Solution");
	}

}

#include <iostream>
(720)#include <cstdio>
#include <string>
(765)#include <sstream>
#define INF 0x3f3f3f3f
using namespace std;
int N,M,K,Ds;
int T;
int graph[2000][2000];
bool used[2000];
int dis[2000];
void dijkstra(int s)
{
    fill(used,used+T,false);
    fill(dis,dis+T,INF);
    dis[s] = 0;
    while(1)
    {
        int v = -1;
        for(int u=1;u<T;u++)
        {
            if(!used[u]&&(v==-1||dis[u]<dis[v]))
                v=u;
        }
        if(v==-1)
            break;
        used[v] = true;
        for(int u=1;u<T;u++)
        {
            dis[u] = min(dis[u],dis[v]+graph[v][u]);
        }
    }
}
int main()
{
    scanf("%d%d%d%d",&N,&M,&K,&Ds);
    T = N+M+1;
    for(int i=0;i<=T;i++)
    {
        for(int j=0;j<=T;j++)
            graph[i][j] = INF;
    }
    for(int i=0;i<K;i++)
    {
        int a;
        int b;
        string str;
        cin>>str;
        if(str[0]=='G')
        {
            istringstream ss(str.substr(1,str.length()-1));
            ss>>a;
            a += N;
        }
        else{
            istringstream ss(str);
            ss>>a;
        }
        cin>>str;
        if(str[0]=='G')
        {
            istringstream ss(str.substr(1,str.length()-1));
            ss>>b;
            b += N;
        }
        else{
            istringstream ss(str);
            ss>>b;
        }
        int dis;
        //cout<<"input:"<<a<<" "<<b<<endl;
        scanf("%d",&dis);
        graph[a][b] = min(graph[a][b],dis);
        graph[b][a] = min(graph[b][a],dis);
    }
    int minisum=0;
    int maxi = -1;
    int ansind = 1;
    for(int i=1;i<=M;i++)
    {
        int sum=0;
        int mini = INF;
        dijkstra(i+N);
        bool out = false;
        for(int j=1;j<=N;j++)
        {
            if(dis[j]>Ds)
            {
                out = true;
                break;
            }
            if(dis[j]<mini)
            {
                mini = dis[j];
            }
            sum+=dis[j];
        }
        if(!out)
        {
            if(mini>maxi)
            {
                maxi = mini;
                minisum = sum;
                ansind = i;
            }
            else if(maxi==mini)
            {
                if(sum<minisum)
                {
                    minisum = sum;
                    ansind = i;
                }
            }
        }
    }
    if(maxi>0)
    {
        cout<<"G"<<ansind<<endl;
        printf("%.1lf %.1lf\n",double(maxi),double(minisum+1e-5)/N);
    }
    else cout<<"No Solution"<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <queue>
#include <exception>
#include <map>
#include <climits>
#define dbg(x) cout << #x ": " << (x) << endl
#define INF INT_MAX
#define mp make_pair
using namespace std;
using LL = long long;

const LL maxn = 1123;

struct Edge{
    int from, to, dist;
    Edge(int from, int to, int dist): from(from), to(to), dist(dist){}
};

bool operator <(const Edge& lhs, const Edge& rhs){
    return lhs.dist > rhs.dist;
}


int main(){
    int N, M, K, D;
    cin >> N >> M >> K >> D;
    vector<vector<Edge>> G(N + M);
    priority_queue<Edge> pq;
    map<pair<int, int>, int> roads;
    for(int i = 0; i < K; i++){
        string s1, s2;
        int p1, p2, dist;
        cin >> s1 >> s2 >> dist;
        if(s1[0] == 'G'){
            // istringstream ss(s1.substr(1));
            // ss >> p1;
            sscanf(s1.c_str() + 1, "%d", &p1);
            p1--;
        }
        else{
            // istringstream ss(s1);
            // ss >> p1;
            sscanf(s1.c_str(), "%d", &p1);
            p1 += M - 1;
        }
        if(s2[0] == 'G'){
            sscanf(s2.c_str() + 1, "%d", &p2);
            p2--;
        }
        else{
            sscanf(s2.c_str(), "%d", &p2);
            p2 += M - 1;
        }
        int a = min(p1, p2), b = max(p1, p2);
        if(a == b){
            // *(int*)0;
            // cout << "self loop!!!" << endl;
            // exit(0);
            continue;
        }
        if(roads.find(mp(a, b)) != roads.end()){
            if(roads[mp(a, b)] < dist){
                // while(true);
                // cout << "shorter path!!!" << endl;
                // exit(0);
                continue;
            }
        }
        G[p1].emplace_back(p1, p2, dist);
        G[p2].emplace_back(p2, p1, dist);
    }
    vector<vector<int>> dists(M, vector<int>(N + M, INF));
    for(int s = 0; s < M; s++){
        pq.emplace(s, s, 0);
        while(!pq.empty()){
            Edge e = pq.top(); pq.pop();
            int u = e.to;
            if(e.dist > dists[s][u]){
                continue;
            }
            dists[s][u] = e.dist;
            for(const auto& ne : G[u]){
                int v = ne.to;
                pq.emplace(s, v, e.dist + ne.dist);
            }
        }
    }
    int chosen = -1;
    double biggest_safe_dist = 0;
    double smallest_avg_dist = INF;
    for(int i = 0; i < M; i++){
        bool ok = true;
        int safe_dist = INF;
        double tot_dist = 0;
        for(int j = M; j < M + N; j++){
            if(dists[i][j] > D){
                ok = false;
                break;
            }
            safe_dist = min(dists[i][j], safe_dist);
            tot_dist += dists[i][j];
        }
        if(!ok) continue;
        double avg_dist = tot_dist / N;
        if(biggest_safe_dist < safe_dist){
            biggest_safe_dist = safe_dist;
            smallest_avg_dist = avg_dist;
            chosen = i;
        }
        else if(
            biggest_safe_dist == safe_dist
                && smallest_avg_dist > avg_dist
        ){
            smallest_avg_dist = avg_dist;
            chosen = i;
        }
    }
    if(chosen != -1){
        cout << "G" << chosen + 1 << endl;
        printf("%.1lf %.1f\n", biggest_safe_dist, smallest_avg_dist);
        // cout << fixed << setprecision(1);
        // cout << biggest_safe_dist + 0.05 << " " << smallest_avg_dist + 0.05 << endl;
        // cout << biggest_safe_dist << " " << smallest_avg_dist << endl;
    }
    else{
        cout << "No Solution" << endl;
    }
}