L3-005 dustbin distribution (30 points)

When we take out the garbage, we all hope that the garbage can is close to ourselves, but no one is willing to stay in the garbage can. Therefore, the location of the dustbin must be the shortest and longest distance to all residential areas, and ensure that each residential area is not too far away from it.

A map of a residential area and the candidate locations of several dustbins are given. Please recommend the most suitable location. If the solution is not unique, the solution with the shortest average distance to all settlements will be output. If such a solution is still not unique, the location with the lowest number is output.

Input format:

Input the first line and give 4 positive integers: n (≤ 103) is the number of residential areas; M (≤ 10) is the number of candidate locations for dustbins; K (≤ 104) is the number of roads between the residential area and the candidate location of the dustbin; D**S is the maximum distance between the residential area and the dustbin that cannot be exceeded. All settlements are numbered from 1 to N, and all trash can candidate locations are numbered from G1 to GM.

Then K lines, each describing a road in the following format:

P1 P2 Dist

P1 and P2 are the numbers of the points at both ends of the road. The ends can be residential areas or garbage can candidate points. Dist is the length of the road and is a positive integer.

Output format:

First, the number of the best candidate location is output in the first line. Then output the minimum distance and average distance from the site to all residential areas in the second line. The numbers are separated by spaces, and one decimal place is reserved. If the solution does not exist, No Solution is output.

Input example 1:

4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2

Output example 1:

G1
2.0 3.3

Input example 2:

2 1 2 10
1 G1 9
2 G1 20

Output example 2:

No Solution

Problem solving ideas:

1. First, explain the meaning of the place with the shortest distance and the longest distance. The location of all garbage cans will have the shortest distance for each residential area, and choose the garbage can with the longest distance among them

2. Select the dij algorithm, take each trash can as the starting point, perform the dij algorithm once, and then you can get the dist array, that is, the shortest distance from the trash can to each residential area, and then jump out of these shortest distances, compare with the shortest distance of other trash cans, and choose the larger one

3. Introduce the stoi function, which can directly convert the string type to int type

Problem solving Code:

#include<bits/stdc++.h>
using namespace std;

const int N = 1011;
int dist[N];
int e[N][N];
int vis[N];
int n,m,k,d;
const int INF =  0x3f3f3f3f;
void dij(int s)
{
	dist[s]=0;
	for(int i=1;i<=n+m;i++)
	{
		int minn=INF, index=-1;
		for(int j=1;j<=n+m;j++)
		{
			if(dist[j]<minn&&!vis[j])
			{
				minn=dist[j];
				index=j;
			}
		}
		if(index==-1)
		break;

		vis[index]=1;
		for(int j=1;j<=n+m;j++)
		{
			if(dist[j]>dist[index]+e[index][j]&&!vis[j])
			{
				dist[j]=dist[index]+e[index][j]; 
			}
		}
	}
	
}

int ansid=-1;
double ansdist=0;
double ansavg=0;

int main()
{
	cin>>n>>m>>k>>d;
	
	fill(e[0],e[0]+N*N,INF);
	
	while(k--)
	{
		string s,s1;
		int a,b;
		double c;
		cin>>s>>s1>>c;
		if(s[0]=='G')
		{
			a=stoi(s.substr(1))+n;	
		}
		else a=stoi(s);
		
		if(s1[0]=='G')
		{
			b=stoi(s1.substr(1))+n;	
		}
		else b=stoi(s1);		
		e[a][b]=e[b][a]=c;

	}
	for(int i=n+1;i<=n+m;i++)
	{
		fill(vis,vis+N,0);
		fill(dist,dist+N,INF);
		dij(i);
		int minn=INF;
		double avg=0;
		for(int j=1;j<=n;j++)
		{

			if(dist[j]<=d)
			{
				minn=min(dist[j],minn);
				avg+=dist[j];
			}
			else
			{
				minn=-1;
				break;
			}
		}

		avg/=n;

		if(minn>ansdist)
		{
			ansdist=minn;
			ansid=i;
			ansavg=avg;
		}
		else if(minn==ansdist)
		{
			if(avg<ansavg)
			{
				ansdist=minn;
				ansid=i;
				ansavg=avg;
			}
		}
	
	}
	if(ansid==-1)
	{
		cout<<"No Solution"<<endl;
	}
	else
	{
		cout<<"G"<<ansid-n<<endl;
		printf("%.1f %.1f",ansdist,ansavg);
	}
	
	
}