题解 P4943 【密室】

· · 题解

惊奇的发现一遍过

本题的走法有三(四)种:

1、哈利去日记,罗恩去金妮

2、哈利去金妮,罗恩去日记

3、哈利自己走

第一、第二中取最短路的最大值;

而第3中情况只要取去1,去2的较短边,因为双向边代表的d[日记][金妮]==d[金妮][日记],即min(d[原点][金妮],d[原点][日记])+d[日记][金妮]

这样题就好做了

之后,读入k即罗恩不能走的就直接将b[i]设为true即可,之后先算罗恩的最短路 总而言之,一共要跑三次最短路,按顺序为:罗恩的,哈利的,从金妮到日记的(哈利) 上代码:

#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<long long,long long> >q;
long long n,m,s,i,cnt,x,y,z,he[1000001],ne[2000001],l[2000001],to[2000001],d[1000001],a1,a2,min1,k;
bool b[1000001];
int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for (i=1;i<=k;i++)
        {
            scanf("%lld",&x);
            b[x]=true;//直接设该点不能走,之后先跑罗恩
        }
    for (i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        cnt++;
        ne[cnt]=he[x];
        to[cnt]=y;
        l[cnt]=z;
        he[x]=cnt;
        cnt++;
        ne[cnt]=he[y];
        to[cnt]=x;
        l[cnt]=z;
        he[y]=cnt;//邻接表
    }
    scanf("%lld%lld",&y,&z);//以y、z储存日记、金妮的位置
    memset(d,127,sizeof(d));
    d[1]=0;
    q.push(make_pair(0,1));
    while (q.size())
    {
        x=q.top().second;
        q.pop();
        if (b[x]) continue;
        b[x]=true;
        for (i=he[x];i!=0 ;i=ne[i])
            if (d[to[i]]>d[x]+l[i])
            {
                d[to[i]]=d[x]+l[i];
                q.push(make_pair(-d[to[i]],to[i]));
            }
    }//罗恩的
    a1=d[y];
    a2=d[z];//记录
    for (i=1;i<=n;i++) b[i]=false;
    memset(d,127,sizeof(d));
    d[1]=0;
    q.push(make_pair(0,1));
    while (q.size())
    {
        x=q.top().second;
        q.pop();
        if (b[x]) continue;
        b[x]=true;
        for (i=he[x];i!=0 ;i=ne[i])
            if (d[to[i]]>d[x]+l[i])
            {
                d[to[i]]=d[x]+l[i];
                q.push(make_pair(-d[to[i]],to[i]));
            }
    }//哈利的
    min1=min(max(a1,d[z]),max(a2,d[y]));//计算1、2两种情况的最小值
    a1=min(d[y],d[z]);
    for (i=1;i<=n;i++) b[i]=false;
    memset(d,127,sizeof(d));
    d[y]=0;
    q.push(make_pair(0,y));
    while (q.size())
    {
        x=q.top().second;
        q.pop();
        if (b[x]) continue;
        b[x]=true;
        for (i=he[x];i!=0 ;i=ne[i])
            if (d[to[i]]>d[x]+l[i])
            {
                d[to[i]]=d[x]+l[i];
                q.push(make_pair(-d[to[i]],to[i]));
            }
    }//从金妮到日记的
    min1=min(min1,d[z]+a1);//再次判断
    printf("%lld",min1);
    return 0;
}

分析之后,这道题也不算难