https://ac.nowcoder.com/acm/contest/331/D
C++版本一
题解:
std
因为K≤15K≤15,一些人看到这个应该直接就状压了,题目放过了这种做法。
但事实上,我们可以将所有额外连边的点再加上起点终点构成一张单独的图。
根据题目数据范围,上述最多一共只有32个点。
随后计算这些点两两间的距离并求起点到终点最短路即可。(因为是有向图,非常好求)
P.S : G++编译环境中,__builtin_popcount(unsigned int)可以$O(1)$计算二进制中该数字1的个数。
时间复杂度O(k2)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
const int mn = 1e3 + 5;
int n, k;
int a[mn], b[mn];
vector<int> p;
inline void addpoint(int x) { p.pb(x); }
int dist[mn];
int main() {
scanf("%d%d", &n, &k);
addpoint(1);
addpoint(n);
for (int i = 1; i <= k; i++) {
scanf("%d%d", &a[i], &b[i]);
if (a[i] > b[i]) swap(a[i], b[i]);
addpoint(a[i]);
addpoint(b[i]);
}
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
memset(dist, 1, sizeof dist); //赋一个足够大值
dist[0] = 0;
for (int i = 0; i < sz(p); i++) {
for (int j = i + 1; j < sz(p); j++) {
for (int l = 1; l <= k; l++) {//这里写的过于粗莽,就O(k^3)了
if (a[l] == p[i] && b[l] == p[j]) {
dist[j] = min(dist[i] + 1, dist[j]);
}
}
dist[j] = min(dist[i] + __builtin_popcount(p[j] - p[i]), dist[j]);
}
}
printf("%d\n", dist[sz(p) - 1]);
return 0;
}
C++版本二
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
int dp[N];
struct node{
int l,r;
bool operator <(const node &S)const{
return r<S.r;
}
}e[N];
int dist(int x){
return __builtin_popcount(x);
}
void dfs(int x,int s,int c){
//cout<<x<<s<<" "<<c<<endl;
if(x==n){
ans=min(ans,c);
return;
}
if(ans<=c)
return;
for(int i=s;i<=cnt;i++){
if(x<=e[i].l){
int res=c+dist(e[i].l-x);
if(e[i].r!=e[i].l)res++;
dfs(e[i].r,s+1,res);
}
}
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%d%d",&n,&m);
//scanf("%d",&t);
//while(t--){}
while(m--){
scanf("%d%d",&k,&q);
if(k<q){
e[++cnt].l=k;
e[cnt].r=q;
}
}
e[++cnt].l=n;
e[cnt].r=n;
ans=INF;
sort(e+1,e+cnt+1);
dfs(1,1,0);
cout << ans << endl;
//cout << "Hello world!" << endl;
return 0;
}