题目传送门

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
int n,lv;
struct Node{int x,y,c,id;}data[110];
bool cmp(Node p1,Node p2)
{
    if(p1.c != p2.c)
        return p1.c > p2.c;
}
vector<Node> pnt[110];
double f[5010][20][20];
double dist(Node p1, Node p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
struct Edge{int v;double w;};
vector<Edge> adj[220];
void init(int l)
{
    int sz = pnt[l].size();
    if(sz == 1)
    {
        adj[pnt[l][0].id * 2 - 1].push_back({pnt[l][0].id * 2,0});
        return;
    }
    for(int i = 0;i < (1 << sz);i++)
        for(int j = 0;j < sz;j++)
            for(int k = 0;k < sz;k++)
                f[i][j][k] = 1e9;
    for(int i = 0;i < sz;i++)
        f[(1 << i)][i][i] = 0;
    for(int s = 1;s < (1 << sz);s++)
        for(int i = 0;i < sz;i++)
        {
            if(s & (1 << i) == 0)
                continue;
            for(int j = 0;j < sz;j++)
            {
                if(s & (1 << j) == 0)
                    continue;
                for(int k = 0;k < sz;k++)
                {
                    if(s & (1 << k) == 0)
                        continue;
                    f[s][i][j] = min(f[s][i][j],f[s ^ (1 << j)][i][k] + dist(pnt[l][k],pnt[l][j]));
                }
            }
        }
    int tmp = (1 << sz) - 1;
    for(int i = 0;i < sz;i++)
        for(int j = 0;j < sz;j++)
        {
            if(i == j)
                continue;
            adj[(pnt[l][i].id) * 2 - 1].push_back({pnt[l][j].id * 2,f[tmp][i][j]});
        }
}
double dis[220];
queue<int> q;
int vis[220];
void spfa()
{
    for(int i = 1;i <= n * 2;i++)
        dis[i] = 1e9;
    dis[0] = 0;
    q.push(0);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(auto v:adj[u])
            if(dis[v.v] > dis[u] + v.w)
            {
                vis[v.v] = 1;
                dis[v.v] = dis[u] + v.w;
                q.push(v.v);
            }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d%d%d",&data[i].x,&data[i].y,&data[i].c);
        data[i].id = i;
    }
    sort(data + 1,data + n + 1);
    lv = 0;
    int tmp = -1;
    for(int i = 1; i <= n; i++)
    {
        if(data[i].c != tmp)
        {
            lv++;
            pnt[lv].push_back(data[i]);
            tmp = data[i].c;
        }
        else
            pnt[lv].push_back(data[i]);
    }
    for(int i = 1;i <= lv;i++)
        init(i);
    for(int i = 2;i <= lv;i++)
        for(auto j:pnt[i - 1])
            for(auto k:pnt[i])
                adj[j.id * 2].push_back({k.id * 2 - 1,dist(j,k)});
    Node t1 = {0,0};
    for(auto i:pnt[1])
        adj[0].push_back({i.id * 2 - 1,dist(t1,i)});
    double ans = 1e9;
    for(auto i:pnt[lv])
        ans = min(ans,dis[i.id * 2]);
    printf("%.2lf\n",ans);
    return 0;
}