93pts求助,#8WA

#8测试点输出181,程序输出209

评测记录

#include<bits/stdc++.h>
using namespace std;
int n,s,dp[305][305],ans=2147483647,sum;
struct Node{
    int u,v,w;
    vector<int>e;
}node;
bool operator<(const Node x,const Node y){
    return x.w<y.w;  
}
priority_queue<Node>q;
int main(){
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<305;i++) dp[i][i]=0;
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        dp[u][v]=w;
        dp[v][u]=w;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
            if(dp[i][j]<=s&&i<=j){
                node.v=i;
                node.u=j;
                node.w=dp[i][j];
                q.push(node);
            }
        }
    }
    while(!q.empty()){
        sum=0;
        node=q.top();
        q.pop();
        for(int i=1;i<=n;i++){
            if(dp[node.u][i]+dp[i][node.v]==node.w){
                node.e.push_back(i);
            }
        }
        for(int i=1;i<=n;i++){
            int k=2147483647;
            for(int j=0;j<node.e.size();j++){
                k=min(k,dp[i][node.e[j]]);
            }   
            sum=max(k,sum);
        }
        ans=min(ans,sum);
    }
    printf("%d\n",ans);
    return 0;
}