Luogu P1078 cultural tour (SPFA)

Title Analysis

I think SPFA directly after reading the question. Then he found himself in a big hole.
The simple SPFA will relax directly in case of shorter results, but there are a lot of limitations in this topic, which are considered as follows:
1. If the culture of the next country has been learned, it cannot be accessed (Updated)
2. If the next national culture despises the learned culture, it cannot be accessed (Updated).
It is not difficult to achieve the above restrictions.

But there is another problem to consider, for example, 2-3 countries are accessible and have been visited. However, when spfa is used, it may be relaxed by aligning the opposite edge 3-2. At this time, because the culture of 2 has been learned and recorded, when relaxing the opposite side, it cannot be updated and the correct result cannot be obtained because the relaxation condition (condition 1 above) is not met.

Solution:
PS
The following "satisfying condition 1" refers to the cultural learning of the next country.
The following does not meet condition 1, which means that the culture of the next country has not been studied.
During SPFA, use bitset to record which culture has been learned and which points have been visited. If (the current node has visited & & does not meet condition 1) | (the current node has not visited & & meets condition 1), it cannot be relaxed.

If you don't want to, you can see the no proposition of two conditions: the current node has visited & & satisfied with condition 1, and the current node has not visited & & not satisfied with condition 1. These relaxation conditions are all tenable.

To sum up, it is actually the XOR that has been visited and studied.

In this way, if the problem is solved, SPFA can be written.

Code overview

#include<bits/stdc++.h>
using namespace std;
const int nmax = 105;
const int INF = 0x3f3f3f3f;
int mp[nmax][nmax];
int cu[nmax];
int dis[nmax];
bitset<nmax> bs[nmax];
bool isin[nmax];
set<int> now;
int n,k,m,s,t;
typedef struct{
    int p;
    bitset<105> b;
    bitset<105> vv;
}status;
void spfa(int st){
    bitset<105> t,vt; t.reset(); t[cu[st]]=1; vt.reset(); vt[st] = 1;
    status ss; ss.b = t; ss.p = st; ss.vv = vt;
    for(int i = 1;i<=n;++i)  dis[i] = i == st? 0 : INF;
    queue<status> q; q.push(ss); isin[st] = 1;
    while(!q.empty()){
        status u = q.front(); q.pop(); isin[u.p] = 0;
        for(int v = 1;v<=n;++v){
            if(mp[u.p][v] == 0 ||  ( (bs[cu[v]]&u.b).any() == 1) || (u.vv[v] ^ u.b[cu[v]]) ){
            }else{
                if(dis[v] > dis[u.p] + mp[u.p][v]){
                    dis[v] = dis[u.p] + mp[u.p][v];
                    if(!isin[v]){
                        t = u.b; t[cu[v]]=1; vt = u.vv; vt[v] = 1;
                        status temp; temp.p = v; temp.b = t; temp.vv = vt;
                        q.push(temp);
                        isin[v] = 1;
                    }
                }
            }
        }
    }
}
int main(){
    scanf("%d %d %d %d %d",&n,&k,&m,&s,&t);
    for(int i = 1;i<=n;++i) scanf("%d",&cu[i]);
    bool ttt;
    for(int i = 1;i<=k;++i){
        bs[i][i] = 1;
        for(int j = 1;j<=k;++j){
            scanf("%d",&ttt);
            bs[i][j] = ttt;
        }
    }
    int u,v,d;
    for(int i = 0;i<m;++i){
        scanf("%d %d %d",&u,&v,&d);
        if(mp[u][v] == 0 || d < mp[u][v])
            mp[u][v] = mp[v][u] = d;
    }
    spfa(s);
    if(dis[t] == INF) printf("-1\n");
    else printf("%d\n",dis[t]);
    return 0;
}

Posted on Wed, 01 Apr 2020 17:24:54 -0700 by madmax