原题名字Currency Exchange Centers
简述题意:
下标从0开始的n个点以及m条边,每条边有一个权值$w$和一个种类$c$,请求出其最小生成树.
如果有多权值相同的最小生成树,则输出使用边的种类最少的方案.即$\sum w$为第一关键字,不同的种类数$C$为第二关键字.
保证有解.
$n,m\in[1,1e5]$

能搜到的题解都是根据边的权值为第一关键字,该种类的边是否出现为第二关键字,使用priority_queuel来实现.
其中一篇题解的代码

unordered_set<string> se;//se中存储已经出现过的种类
struct edge
{
    int x, y;
    string s;
    int val;
    edge(int a = 0, int b = 0, string c = "", int d = 0) : x(a), y(b), s(c), val(d){}
    bool operator < (const edge b) const 
    {
        return val != b.val ? val > b.val : se.find(s) == se.end();
    }
}e[maxn << 1];

但是这样似乎不能保证一定是最优解

hack数据

3 3
0 1 B 1
0 1 A 1
1 2 B 3

这种做法无法判断这种情况.实际上,因为当前的选择会影响到后面的优先级,贪心的正确性似乎无法保证了.

请问是否存在正确的做法?又或者说是这道题是个假题?