Nothing to fear

The best time to plant a tree was ten years ago, followed by now!

You don't want to train for the hard work you have made in going out early and returning home late. When you feel too tired but still have to bite your teeth and stick to it, that is, you are chasing your dreams. Don't care what the end point is. You should enjoy the process of the journey. Maybe you can't achieve your dreams, but something bigger will follow. mamba out~

2020.7.13

I will pursue the dream of youth and never give up with confidence!

Gas Station

Test site:

General idea of the topic

To establish a gasoline station, the shortest distance between the gasoline station and each household is required to be as short as possible (Dijkstra can not run away). Secondly, it must ensure that all households are within the service range of the refueling

Give you a map and ask for the best place to build a gas station. If there is more than one answer, output the one with the shortest average distance. If it is repeated, output the one with the lowest number

Output content: 1 Best station number. 2. the shortest and average distance from the station to all houses

analysis

Points needing attention:

• Process the number of the gas station, and make the gas station number from n+1 to n + m
• From [n + 1, N + m] do Dijkstra one by one from this starting point to get different answers for comparison
• It seems that we can't use the chained forward star to store edges. There may be many repeated edges with different weights. In other words, this should not affect us. However, the last test point of the forward star can't pass, and we can't find any bug s. If netizens are lucky enough to see it, they can also consider it, and then change it to the way of link matrix to AC directly.

Full code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 2005;
int n , m , k ,ds;
int e[N][N];
int dis[N] , vis[N];
struct node{
	int id = -1, mindis = 0;
	double avg = 0x3f;
};
node res;
void Dijkstar(int s)
{
	memset(dis , 0x3f , sizeof dis);
	memset(vis , 0 , sizeof vis);
	dis[s] = 0;
	for(int k = 0;k < n + m ;k ++)
	{
		int x = -1;
		for(int i = 1;i <= n + m;i ++)
		{
			if(!vis[i] && (x == -1 || dis[i] < dis[x]))
				x = i;
		}
		vis[x] = 1;
		for(int i = 1; i <= n + m; i ++)
		{
			int y = i , w = e[x][i];
			if(vis[y])continue;
			dis[y] = min(dis[y] , dis[x] + w);
		}
	}
	double avg = 0 ;int mindis = dis[1];
	for(int i = 1;i <= n ;i ++)
	{
		if(dis[i] > ds)return;
		mindis = min(dis[i] , mindis);
		avg += 1.0 * dis[i];
	}
	avg = avg / n;
	//printf("id = %d avg = %f mindis = %.1f\n", s,avg , (double)mindis);
	if (mindis > res.mindis) {
		res.id = s;
		res.mindis = mindis;
		res.avg = avg;
	}
	else if(mindis == res.mindis && avg < res.avg) {
		res.id = s;
		res.avg = avg;
	}
}
int main()
{
	memset(e , 0x3f , sizeof e);
	for(int i = 0;i < N;i ++)e[i][i] = 0;
	cin >> n >> m >> k >> ds;
	int a , b , c;string sa , sb;
	// The id of the gas station from N + 1 - > N + m is G1, G2
	for(int i = 0;i < k;i ++)
	{
		cin >> sa >> sb >> c;
		if(sa[0] == 'G')a = stoi(sa.substr(1)) + n;
		else a = stoi(sa);
		if(sb[0] == 'G')b = stoi(sb.substr(1)) + n;
		else b = stoi(sb);
		e[a][b] = e[b][a] = c;
	}//Dijkstra once for each gas station
	for(int i = n + 1;i <= n + m;i ++){
		Dijkstar(i);
	}
	if(res.id == -1)cout << "No Solution" << endl;
	else printf("G%d\n%.1f %.1f", res.id - n , (double)res.mindis ,res.avg);
	return 0;
}