3073. 道路排序

三元组排序，写好cmp即可，与图无关，不需要建图

include

using namespace std;

define INF 0x3f3f3f3f

int T,n,m;
struct path
{
int from,to,len;
};
vector V;
int cmp(const path& aa,const path& bb)
{
if(aa.len!=bb.len) return aa.len>bb.len;
else if(aa.from!=bb.from) return aa.from>n>>m;
V.clear();
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
V.push_back((path){x,y,z});
}
sort(V.begin(),V.end(),cmp);
for(int i=0;i<V.size();i++) printf(“(%d,%d,%d)\n”,V[i].from,V[i].to,V[i].len);
return;
}
int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

一开始以为要建图，读完题发现 $n$ 根本是没有用的。就是简单自定义排序。

struct Edge {
    uint32_t src, dest, val;
    bool operator<(Edge const &rhs) const {
        return val == rhs.val ? src == rhs.src ? dest < rhs.dest : src < rhs.src : val > rhs.val;
    }
};

int main() {
    uint32_t t; std::cin >> t;
    for (uint32_t query = 0; query < t; ++query) {
        printf("case #%u:\n", query);
        uint32_t n, m; std::cin >> n >> m;
        std::vector<Edge> roads(m);
        for (auto &i : roads)
            std::cin >> i.src >> i.dest >> i.val;
        std::sort(roads.begin(), roads.end());
        for (auto const &i : roads)
            printf("(%u,%u,%u)\n", i.src, i.dest, i.val);
    }
}