2021/08/20 14:22
思路:dijkstra,枚举,排序
题意:给出一无向图,其中有一些点是垃圾桶的候选点,剩下是居民位置。要选一个垃圾桶,它到居民距离的最小值最大,同时最大值不超过最大服务距离,如果有多个这样的垃圾桶,选距垃圾桶平均距离最小的那一个,如果还有多个就选编号最小的那个垃圾桶
居民到一个垃圾桶的距离,可以反向看做一个垃圾桶到每个居民的距离,进而转化成了单源最短路径
还有一点比较坑的就是,一开始我以为选择了一个垃圾桶,在计算最短路的时候应该屏蔽掉其他垃圾桶,但是没想到是都算的
点数并不多,所有直接用邻接矩阵存图,第i个垃圾桶存成编号为n + i
,然后做k次dijkstra
即可,每次做完根据题意更新答案,这里直接对dist[]
排序,很方便找到距离最大值和最小值
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1020, INF = 0x3f3f3f3f;
int n, m, k, s;
int G[N][N], dist[N];
bool vis[N];
int ans, ansd, sumd;
void dijkstra(int u)
{
memset(vis, 0, sizeof vis);
memset(dist, 0x3f, sizeof dist);
dist[u] = 0;
int sum = 0;
while(true)
{
int t = -1;
for(int i = 1; i <= n + m; i++)
if(!vis[i] && (t == -1 || dist[t] > dist[i]))
t = i;
if(t == -1)
break;
vis[t] = true;
if(t >= 1 && t <= n)
sum += dist[t];
for (int i = 1; i <= n + m; i ++ )
{
if(dist[i] > dist[t] + G[t][i])
dist[i] = dist[t] + G[t][i];
}
}
sort(dist + 1, dist + n + 1);
if(dist[n] <= s)
{
if((dist[1] > ansd) || (dist[1] == ansd && sum < sumd))
{
ans = u - n;
sumd = sum;
ansd = dist[1];
}
}
}
int main()
{
memset(G, 0x3f, sizeof G);
cin >> n >> m >> k >> s;
while(k--)
{
int a, b, c;
string sa, sb;
cin >> sa >> sb >> c;
if(sa[0] == 'G')
a = n + stoi(sa.substr(1));
else
a = stoi(sa);
if(sb[0] == 'G')
b = n + stoi(sb.substr(1));
else
b = stoi(sb);
G[a][b] = G[b][a] = min(G[a][b], c);
}
for (int i = 1; i <= m; i ++ )
dijkstra(n + i);
if(ansd == 0)
cout << "No Solution";
else
{
cout << "G" << ans << endl;
printf("%.1lf %.1lf\n", (double)ansd, (double)sumd / n + 1e-6);
}
return 0;
}