题解：P1078 [NOIP2012 普及组] 文化之旅

· · 题解

声明：

本题，看了题解区发现只有 1 篇 dijkstra 的算法，于是有了这篇题解。

因为本题不一定存在正确的解法换句话说：就是错题，所以有 hack 也很正常吧。

思路：

本题使用的是 dijkstra 算法求最短路，但是这道题不同的一点是，这里面出现了文化歧视，文化不重复学习等。我们可以加入标记来让本题可以愉快地使用 dijkstra 算法。

代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=105;
struct node{
    int v,w;
};
struct nodee{
    int u,d;
    int used[N];//哪种语言使用过了 
    bool operator<(const nodee &A)const{
        return A.d<d;
    }
};
vector<node>edge[N];
bool vis[N],qs[N][N];
int dis[N],c[N];
int n,f,t,w,m,u,st,en,k,v;
void dijkstra(int st){
    priority_queue<nodee>q;
    nodee ccf;
    ccf.u=st;
    ccf.d=0;
    for(int i=1;i<=k;i++) ccf.used[i]=0;
    q.push(ccf);//封装存储 
    fill(dis,dis+1+n,1e9);//最大值初始化 
    dis[st]=0;
    while(!q.empty()){
        u=q.top().u;
        nodee us=q.top();
        q.pop();
        if(vis[u]||us.used[c[u]]) continue;
        vis[u]=1;
        us.used[c[u]]=1;
        for(int i=1;i<=k;i++)
            if(qs[c[u]][i]) us.used[i]=1;//歧视 
        for(node e:edge[u]){
            v=e.v;
            w=e.w;
            if(us.used[c[v]]) continue; 
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    ccf.d=dis[v];
                    ccf.u=v;
                    for(int j=1;j<=k;j++) ccf.used[j]=us.used[j];
                    q.push(ccf);
                }
            }
        }
    }
    if(dis[en]!=1e9) cout<<dis[en];
    else cout<<-1;
    return ;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>m>>st>>en;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++) cin>>qs[i][j];
    while(m--){
        cin>>f>>t>>w;
        edge[f].push_back(node{t,w});
        edge[t].push_back(node{f,w});
    }
    dijkstra(st);
    return 0;
}

尾言：

本题不保证存在可以通过满足本题数据范围的任意数据做法。由于测试数据过水，可以通过此题的程序不一定完全正确（算法时间复杂度错误、或不保证正确性）。本题题目和数据仅供参考。本题不接受添加 hack 数据。
本题为错题。不建议尝试或提交本题。关于此类题目的详细内容

所以，我的代码没有过样例，但是 AC 了。

如果是我代码的问题，希望大佬指出。

玄学合集：

玄学1 Floyd 92pts
玄学2 dijkstra+A* 没过样例，但是 AC 了
玄学3 正搜对 4 个，逆搜对 3 个
玄学4 第 10 个点，本地 RE，洛谷神速
玄学5 没有判断条件 AC
玄学6 dfs 对 4 个点，删掉回溯 AC
玄学7 样例没过 AC
玄学8 倒搜没有该判断 AC 了
玄学9 不合理的 AC，加了 vis 直接卡到 0ms
玄学10 第 10 个点 1008ms
以上是作者翻阅讨论区得到的玄学合集。