[洛谷题解] P1078 文化之旅

发布于 2018-11-16  181 次阅读 

来源：洛谷
编号：P1078
地址：https://www.luogu.org/problemnew/show/P1078

题目描述

NOIP普及组 2012 T4

比较复杂的最短路题目

解题思路

听说这道题是错题，数据水得不要不要的？那我可要拿出骗分大法了！

暴力搜索！

首先，可以明确，由于使者太懒，任何国家都可以被视为排斥相同文化的外来人。

这道题刚开始看起来像是最短路（也确实是）。最短路的算法大家经常谈论的都涉及到点上标签的迭代，但是最短路实际上有种贪心做法，就是 UCS（Uniform cost search, 亦称最短路Label Setting），思想同BFS，只是使用优先队列，总是将离起点最近的节点排在队列的前面，这样，总是可以保证前沿的节点到起点的距离相对一致。

但是Label Setting充其量就是暴力搜索。我们用结构体_entry来存储搜索状态，包含到起点的距离、当前所在国家和一个 STL set——已学习的文化（这当然是最暴力的做法）。每当扩展一个在优先队列中的节点时，要检查其相邻节点的文化与已学习文化的set是否相容。

初始状态，距离为0，当前位置为起点，已学习的文化只有一个——起点的文化。

当搜索算法找到终点时，返回距离即可。如果队列空了还没找到，显然就返回-1.

以下是坑点（很重要）

36分——小于号重载错误

第一次提交36分纯属忘记了优先队列会将大的元素排在前面，因此将_entry的小于号直接定义为离起点距离的小于号（应该改为大于等于，这样距离小的entry会排在前面）。

44分——在找到终点时就结束搜索

Label Setting不能在找到终点时就结束搜索。想象有两个节点P, Q，搜索后距离起点的距离分别为33, 34，两个节点均为下一步就能到达终点，P到达终点长度为10，Q为1.

根据Label Setting的规则，P在Q之前被展开，因此找到终点，返回最短路为43。但是显然从Q到终点的总距离只有35。显然错了。

正确的做法应该是在终点即将离开优先队列时返回最短路。

92分——被10号数据卡到

事实证明其他数据都很水，只有10号数据无解而且能诱导搜索算法运行很长一段时间。

方法：骗分。当出队操作执行超过800次时强制结束搜索，返回-1.

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll r[101][101]; //文化的排斥关系 r[i][j]
struct _country{
    ll r; //文化
    vector<pair<ll,ll> > n; //通往其他国家的路线
}c[101];
ll n,m,k,s,t; //如题
struct _entry{
    ll c; //国家
    ll l; //路径长度
    set<ll> study; //已学习
    _entry(){
        c=-1;l=0;
    }
    _entry(ll _c,ll _l,ll _i){
        c=_c;l=_l;
        study.insert(_i);
    }
    bool operator<(const _entry &other) const {
        return l>=other.l;
    }
};
priority_queue<_entry> que;
 
ll checkIfError(set<ll> studies,ll c) { //检查已学习数组是否与新文化冲突
    for(ll i=1;i<=k;i++)
    {
        if(r[c][i] && studies.count(i)) return true;
    }
    return false;
}
 
ll search() {
    ll elasped=0;
    que.push(_entry(s,0,c[s].r)); //初始
    while(!que.empty()) {
        _country curr=c[que.top().c]; //出发点国家节点
        _entry ent=que.top(); //出发点的Entry信息
        elasped++;
        if(elasped>800) return -1;
        if(ent.c==t) {
            return ent.l;
        }
        que.pop();
        for(ll i=0;i<curr.n.size();i++) {
            _entry tmp=ent;
            tmp.l+=curr.n[i].second;
            tmp.c=curr.n[i].first;
            //cout<<"From "<<ent.c<<" to "<<tmp.c<<endl;
            if(checkIfError(ent.study,c[tmp.c].r)) continue; //判断冲突
            tmp.study.insert(c[tmp.c].r);
            que.push(tmp);
        }
    }
    return -1;
}
 
int main()
{
    cin>>n>>k>>m>>s>>t;
    for(ll i=1;i<=n;i++) {
        cin>>c[i].r; //输入文化
    }
    for(ll i=1;i<=k;i++) {
        for(ll j=1;j<=k;j++) {
            cin>>r[i][j];
            if(i==j) r[i][j]=1; //不能学习多次，即所有文化排斥自己
        }
    }
    for(ll i=1;i<=m;i++) {
        ll x,y,z;
        cin>>x>>y>>z;
        c[x].n.push_back(make_pair(y,z)); //输入路径
        c[y].n.push_back(make_pair(x,z));
    }
    cout<<search()<<endl;;
}
赏

undefined