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

· · 题解

T4 题目传送门

思路

一道最短路问题。不会最短路算法的同学可以先去这里学习一下。

由于 CCF 会卡 spfa（本题没卡），故我们选择 dijstrka 算法进行求解。由于题目中要求不能重复学习一个文化且有些文化不被“包容”，那么我们选择用 set 记录从 s 城市开始到当前位置所有学习过的文化。

这个程序的时间复杂度为 \mathcal{O}(K(N+M)\log NM)，约为 10^6\times \log 10^6=2\times 10^7，足以通过此题。

代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
ll read(){//快读优化，不加也行。
    ll k=0;bool flag=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')flag=0;c=getchar();}
    while(c>='0'&&c<='9'){k=(k<<1)+(k<<3)+(c^48);c=getchar();}
    if(flag)return k;return -k;
}
const int N=110;
int n,k,m,s,t,c[N],dis[N];
bool a[N][N];
vector<pii>g[N];
struct node{
    int step,x;
    set<int>st;
    bool operator<(const node a)const{return step>a.step;}//优先队列需要定义结构体的排序方式。记得是大根堆，所以符号反着写。
};priority_queue<node>q;
bool check(set<int>st,int now){//判断学习过的文化是否满足到达这个城市。
    for(int i=1;i<=k;++i){
        if(!a[now][i])continue;//没有要求不能进入。
        if(st.find(i)!=st.end())return 0;//要求不能进入且学习过这个文化，就到达不了。
    }
    return 1;//不是不能到达就是可以到达。
}
int main(){
    cin>>n>>k>>m>>s>>t;
    for(int i=1;i<=n;++i)c[i]=read();
    for(int i=1;i<=k;++i){
        for(int j=1;j<=k;++j)a[i][j]=read();
    }
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        g[u].pb({w,v});//双向建边。
        g[v].pb({w,u});
    }
    memset(dis,0x3f,sizeof dis);//记得初始化最大值。
    dis[s]=0;
    set<int>st;
    st.insert(c[s]);
    q.push({0,s,st});
    while(q.size()){
        node now=q.top();
        q.pop();
        for(auto i:g[now.x]){
            if(dis[i.se]>dis[now.x]+i.fi){//如果不是最短路径再判断。
                if(st.find(c[i.se])==st.end()&&check(now.st,c[i.se])){//还要判断不能重复学习一种文化（&& 号前的部分）。
                    dis[i.se]=dis[now.x]+i.fi;//更新到达这个点的最短路。
                    now.st.insert(c[i.se]);//学习这个文化。
                    q.push({dis[i.se],i.se,now.st});
                    now.st.erase(c[i.se]);//“忘掉”这个文化，便于遍历其他城市。
                }
            }
        }
    }
    if(dis[t]==0x3f3f3f3f)cout<<-1;//走不通输出 -1。
    else cout<<dis[t];
    return 0;
}

AC 记录