A题

这个题我觉得好难啊，不过A掉的人不少。我的想法就是类似最小生成树的prim算法，不过这里不再是找与已联通的点集相连的最小边，而是找与某点相连的最小边。这样，只需要找n-1次就可以找到一条将所有点连接起来的单向路径，然后按照题意加上终点到起点的距离就可以了。

#include <bits/stdc++.h>

using namespace std;
struct node
{
    int x,y;
}p[400];
int vis[30];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        int d,l;int n;
        scanf("%d%d",&d,&l);
        scanf("%d%d",&p[0].x,&p[0].y);
        scanf("%d",&n);
        for(int i = 1;i <= n;++i) scanf("%d%d",&p[i].x,&p[i].y);
        int ans = 0;vis[0] = 1;int k = 0;
        for(int i = 1;i <= n;++i)///总共n + 1个点所以循环n次
        {
            int u = 0;
            int maxn = 100000;
            for(int j = 0;j <= n;++j)///找到与k点相连的最短点
            {
                if(!vis[j]&&maxn > abs(p[j].x - p[k].x) + abs(p[j].y - p[k].y))
                {
                    maxn = abs(p[j].x - p[k].x) + abs(p[j].y - p[k].y);
                    u = j;
                }
            }
            if(maxn != 100000)
            {
                vis[u] = 1;
                k = u;
                ans += maxn;
            }
        }
        ans += abs(p[k].x - p[0].x) + abs(p[k].y - p[0].y);
        printf("The shortest path has length %d\n",ans);
    }
    return 0;
}