求助P4943 Dij堆优化 2 10两点WA
  • 板块P4943 密室
  • 楼主LiuXinru
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/9/26 22:03
  • 上次更新2023/11/5 12:33:08
查看原帖
求助P4943 Dij堆优化 2 10两点WA
295769
LiuXinru楼主2020/9/26 22:03
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double D;
const int N=5e4+10;
const int M=1e5+10;
const int INF=1e9;
struct node
{
    int t,l,next;
}edge[M*2];
int head[N],dis[N],tot,st,nd,a[N],flag;
bool vis[N];
int n,m,k;
struct Rec
{
    int id,dis;
    bool operator<(const Rec &tmp)const
    {
        return dis>tmp.dis;
    }
};
priority_queue<Rec> q;
void Init()
{
    memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(a,0,sizeof(a));
    tot=0;
}
void add(int f,int t,int l)
{
    tot++;
    edge[tot].t=t;
    edge[tot].l=l;
    edge[tot].next=head[f];
    head[f]=tot;
}
void dist()//模板
{
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    memset(vis,false,sizeof(vis));
    dis[st]=0;
    Rec rec;
    rec.id=st;
    rec.dis=0;
    q.push(rec);
    while(!q.empty())
    {
        int u=q.top().id;
        q.pop();
        if(vis[u])
            continue;
        vis[u]=true;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].t;
            int w=edge[i].l;
            if(dis[v]>dis[u]+w&&a[v]<=flag)//正在跑的人是否可以进入这个房间
            {
                dis[v]=dis[u]+w;
                Rec rec;
                rec.id=v;
                rec.dis=dis[v];
                q.push(rec);
            }
        }
    }
}
int main()
{
    Init();
    int x,y;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {
        int o;
        cin>>o;
        a[o]=1;
    }

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    cin>>x>>y;
    int ans1,ans11,ans2,ans22,ans;
    
    flag=1;//标记 正在跑的是哪个人
    st=1;
    dist();
    ans1=dis[x];
    ans11=dis[y];
    // 哈利 去两个点分别需要的最小时间
    flag=0;
    dist();
    ans2=dis[x];
    ans22=dis[y];
    // 罗恩 去两个点分别需要的最小时间
    ans=min(max(ans1,ans22),max(ans2,ans11));// 两人须分别去两个房间 所以取两个最大值的最小
    cout<<ans<<endl;
    return 0;
}

跪求指点,拜谢

2020/9/26 22:03
加载中...