C 正方体比例： 1:2:3（未开根号）

直接8个点两两算边～
12/12/4
而且长度符合1，2，3比例（我的距离没有开方，实际上是1，√2，√3）

#include<bits stdc++.h>
using namespace std;
int const N=107;
int t;
struct L{
    int x,y,z;
}a[N];
int pan(L a,L b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)
           +(a.z-b.z)*(a.z-b.z);
}
map<int,int>mp;
map<int,int>::iterator it;
int main(){
    cin &gt;&gt; t;
    while(t--){
        memset(a,0,sizeof a);
        for(int i=1;i&lt;=8;++i){
            cin &gt;&gt; a[i].x &gt;&gt; a[i].y &gt;&gt; a[i].z;
        }
        for(int i=1;i&lt;=8;++i){
            for(int j=1;j&lt;=8;++j){
                if(i==j) continue;
                int z=pan(a[i],a[j]);
                mp[z]++;
            }
        }
        it=mp.begin();
        int z=it-&gt;first;
        if(mp.size()==3&amp;&amp;mp[z]==24&amp;&amp;mp[z*2]==24&amp;&amp;mp[z*3]==8){
            cout &lt;&lt; "YES\n";
        }
        else cout &lt;&lt; "NO\n";       
        mp.clear();
    }    
    return 0;
}

J dijstra + 完全背包

每次只能拿一个 + 无限数量 + 时间代价 （完全背包）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=3e3+7;
int const M=3e3+7;
struct node{
    int a,next,len;
}e[M<<1];
int cnt,head[N];
void add(int x,int y,int len){
    e[++cnt].a =y;
    e[cnt].len=len;
    e[cnt].next =head[x];
    head[x]=cnt;
}
struct L{
    int a,dis;
    friend bool operator<(L a,L b){
        return a.dis > b.dis;
    }
};
int n,m,t;
int vis[N],dis[N];
void dijstra(int s){
    memset(dis,0x3f,sizeof dis);
    priority_queue<L>pq;
    pq.push((L){s,0});dis[s]=0;
    while(!pq.empty()){
        int u=pq.top().a;pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i!=0;i=e[i].next){
            if(vis[e[i].a]) continue;
            if(dis[u]+e[i].len<dis[e[i].a]){
                dis[e[i].a]=dis[u]+e[i].len*2;
                pq.push((L){e[i].a,dis[e[i].a]});
            }
        }    
    }
}
ll f[M];
int w[N];
int main(){
    cin >> n >> m >> t;
    for(int i=2;i<=n;++i) cin >> w[i];
    for(int i=1;i<=m;++i){
        int a,b; cin >> a >> b;
        add(a,b,1);add(b,a,1);
    }
    dijstra(1);
    m=t;
    for(int i=2;i<=n;++i){
        for(int j=dis[i];j<=m;++j){
            f[j]=max(f[j],f[j-dis[i]]+w[i]);
        }
    }
    for(int i=1;i<=m;++i){
        cout << f[i] << " ";
    }
    return 0;
}

M 签到题