WA on sub 4,5 求助
查看原帖
WA on sub 4,5 求助
507348
__vector__楼主2022/12/25 21:23
// 先建跑最短路,求出每个点到终点的距离,
// 然后求出哪些点在最短路上。  
// 然后从起点每一步贪心找,离终点最近的点(即权值最大)  
#include <bits/stdc++.h>
using namespace std;
#define int long long
void read(int& x)
{
    x=0;
    char ch=getchar();
    while(!isdigit(ch))
    {
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
}
void write(int x)
{
    if(x>=10)
    {
        write(x/10);
    }
    putchar(x%10^48);
}
const int maxn=4e5+5;
int n,m,S,B,F;
int head[maxn<<1];
struct EDGE
{
    int to,val,nxt;
}edge[maxn<<1];
int ecnt;
void add(int u,int to,int val)
{
    edge[++ecnt].to=to;
    edge[ecnt].val=val;
    edge[ecnt].nxt=head[u];
    head[u]=ecnt;
}
int dis_to_F[maxn];
bool vis[maxn];
void dijkstra()
{
    memset(dis_to_F,0x3f3f3f3f,sizeof dis_to_F);
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
    que.push(make_pair(0,F));
    dis_to_F[F]=0;
    while(!que.empty())
    {
        int u=que.top().second;
        que.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(dis_to_F[to]>dis_to_F[u]+edge[i].val)
            {
                dis_to_F[to]=dis_to_F[u]+edge[i].val;
                que.push(make_pair(dis_to_F[to],to));
            }
        }
    }
}
int temp[maxn];
int temptop;
int path_list[maxn],pltop;
void dfs(int u)
{
    path_list[++pltop]=u;
    vis[u]=1;
    if(u==F)
    {
        return;
    }
    temptop=0;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(vis[to])continue;
        if(dis_to_F[to]+edge[i].val==dis_to_F[u])
        {
            temp[++temptop]=to;
        }
    }
    sort(temp+1,temp+temptop+1);
    dfs(temp[1]);
}
int S_to_pth[maxn];
void dijkstra2()
{
    memset(vis,0,sizeof vis);
    memset(S_to_pth,0x3f3f3f3f,sizeof S_to_pth);
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
    que.push(make_pair(0,S));
    S_to_pth[S]=0;
    while(!que.empty())
    {
        int u=que.top().second;
        que.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(S_to_pth[to]>S_to_pth[u]+edge[i].val)
            {
                S_to_pth[to]=S_to_pth[u]+edge[i].val;
                que.push(make_pair(S_to_pth[to],to));
            }
        }
    }
}
int B_to_pth[maxn];
void dijkstra3()
{
    memset(vis,0,sizeof vis);
    memset(B_to_pth,0x3f3f3f3f,sizeof B_to_pth);
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
    que.push(make_pair(0,B));
    B_to_pth[B]=0;
    while(!que.empty())
    {
        int u=que.top().second;
        que.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(B_to_pth[to]>B_to_pth[u]+edge[i].val)
            {
                B_to_pth[to]=B_to_pth[u]+edge[i].val;
                que.push(make_pair(B_to_pth[to],to));
            }
        }
    }
}
signed main()
{
  //  scanf("%d%d%d%d%d",&n,&m,&S,&B,&F);
    read(n);
    read(m);
    read(S);
    read(B);
    read(F);
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
      //  scanf("%d%d%d",&u,&v,&w);
        read(u);
        read(v);
        read(w);
        add(u,v,w);
        add(v,u,w);
    }    
    dijkstra();
    memset(vis,0,sizeof vis);
    dfs(S);
    dijkstra2();
    dijkstra3();
    long double ans2=100000000000.0;
    for(int i=1;i<=pltop;i++)
    {//遍历从 S 出发要走的路径
        int node=path_list[i];
        long double s=(long double)S_to_pth[node]/2.0;
        long double b=(long double)B_to_pth[node]/3.0;
        // S_to_pth[node] = S 到这个节点的距离
        // B_to_pth[node] 同理  
      //  printf("1 S_to_pth[%d]: %d B_to_pth[%d]: %d\n",node,S_to_pth[node],node,B_to_pth[node]);
        if(b<=s)
        {
     //       printf("2 node: %d ans: %lf\n",node,b+(S_to_pth[node]-b*2.0)/5.0);
      //      printf("2 b: %lf S_to_pth[%d]: %d\n",b,node,S_to_pth[node]);
            
            ans2=min(ans2,b+((long double)S_to_pth[node]-b*2.0)/5.0);
        }
    }
    long double firtime=(long double)B_to_pth[S]/3.0;// B 走到 S 时间
    long double ssum=firtime*2.0;
    long double as=ssum/(3.0-2.0)+firtime;
    if(as*2.0<(long double)dis_to_F[S])
    {
        ans2=min(ans2,as);
    }
    if(abs(ans2-100000000000.0)<=1e-9)
    {
        puts("YES");
        long double ans1=((long double)dis_to_F[B]/3.0-(long double)dis_to_F[S]/2.0)*3.0;
        stringstream stre;
        stre<<fixed<<ans1;
        string ans;
        stre>>ans;
        while(ans.size()>1&&(ans[ans.size()-1]=='0'||ans[ans.size()-1]=='.'))ans.pop_back();
        cout<<ans;
    }
    else
    {//这里挂了
        
        puts("NO");
        stringstream stre;
        stre<<fixed<<ans2;
        string ans;
        stre>>ans;
        while(ans.size()>1&&(ans[ans.size()-1]=='0'||ans[ans.size()-1]=='.'))ans.pop_back();
        cout<<ans;
    }
    return 0;
}
2022/12/25 21:23
加载中...