本题传送门
谢谢你，多远最短路
解题思路
这题忒阴了，反正我是没看出来多源最短路，做得时候给我裹死了，最后看题解是多源最短路
我们从题意中发现，显然是个有向图。题目要求最后分别算出男女中异性缘最好的两个人，如果同性中有异性缘一样高的，就按序号递增顺序输出。
又因为要取推导值中的最小值，确实对应着最短路中的松弛操作。
最后还要根据性别分别取最小值，有多个还要递增输出
直接上代码吧,确实要多看图论问题。
ac✅️代码
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
const long long INF = 1e15;
long long dist[510][510];
char gender[510];
int main()
{int n;cin>>n;for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= n ; j++){if(i == j) dist[i][j] = 0;else dist[i][j] = INF;}}for(int i = 1 ; i <= n ; i++){int k;cin>>gender[i]>>k;for(int j = 0 ; j < k ; j++){int friend_id ;long long d ;char colon ;cin>>friend_id>>colon>> d;dist[i][friend_id] = d;//建立关系图}}for(int k = 1; k <= n ; k++)//n次松弛{for(int i = 1 ; i <= n ; i++){if(dist[i][k] == INF) continue;for(int j =1 ; j <= n ; j++){dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);}}}vector<long long> max_d(n + 1 , 0);for(int i = 1 ; i <= n ; i ++)//对i个人求他（她）的最大异性缘{long long cur_max = 0 ;for(int j = 1 ; j <= n ; j++){if(gender[i] != gender[j]){ cur_max = max(cur_max , dist[j][i]);}}max_d[i] = cur_max;//不一定要开一个二维数组，每个数组对应一个人//开一维也可以，只不过要提前开好空间。}auto find_lovers = [&](char g)//性别作为参数{long long min_of_max = INF;for(int i = 1 ; i <= n ; i++){if(gender[i] == g){min_of_max = min(min_of_max , max_d[i]);//这里采取的是先找最大值，不过还有一种方法是用clear函数，不过clear函数复杂度为N}}vector<int> res;for(int i = 1 ; i <= n ; i++){if(gender[i] == g && max_d[i] == min_of_max)res.push_back(i);}for(int i = 0 ; i < res.size() ; i ++){cout<<res[i];if(i != res.size() - 1) cout<<" ";}cout<<endl;};find_lovers('F');find_lovers('M');return 0;}