Problem

有向图

求路径 $1\rightarrow 2 \rightarrow 1$ 至少经过几个点

$n,m\leq 200$

Solution

解法 1：

选择直接爆搜到 2 点后跑 dijkstra
剪枝就是爆搜的点超过了 ans 之后就剪掉
显然是能被卡掉的辣（逃）

但把剪枝优化一下还是比较难卡哒

考虑求出 1 ->2->1 中 2 ->1 必须单独算的点的数目
即 1 ->2 的必经点不在 2 ->1 的必经点中

emmm... 支配树？

这个暴力算一下还是可以哒

解法 2（标算）：

考虑 $w[i][j]$ 为 $i\rightarrow j$ 的最短路

$dp[i][j]$ 为 $1\rightarrow i\rightarrow j\rightarrow 1$ 至少经过多少点

转移：$dp[i][j]=min(dp[x][y]+w[y][j]+w[j][i]+w[i][x]-1)$

即新增的路径和被重复经过的点 $i$。

dijkstra 跑这个 dp 的话，是 $O(n^2\log n^2)$ 大概。

Code（未优化解法 1）:

// Code by ajcxsu
// Problem: kampanja

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;

const int N=210, M=210;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
char vis[N];

int dist[N];
char S[N];
typedef pair<int, int> mpair;
int dij(int s, int t) {
    priority_queue<mpair, vector<mpair>, greater<mpair> > pq;
    CLR(S, 0), CLR(dist, 0x3f);
    dist[s]=0;
    pq.push(mpair(0, s));
    int na;
    while(!pq.empty()) {
        na=pq.top().second, pq.pop();
        if(S[na]) continue;
        S[na]=1;
        if(na==t) break;
        for(int u=h[na];u;u=nexp[u])
            if(!S[to[u]] && dist[to[u]]>dist[na]+(!vis[to[u]]))
                dist[to[u]]=dist[na]+(!vis[to[u]]), pq.push(mpair(dist[to[u]], to[u]));
    }
    return dist[t];
}
int ans=0x3f3f3f3f, nlen;
void dfs(int x, int k) {
    if(k>=ans) return;
    vis[x]=1;
    if(x==2) {
        ans=min(ans, dij(2, 1)+k);
        vis[x]=0;
        return;
    }
    for(int u=h[x];u;u=nexp[u])
        if(!vis[to[u]]) dfs(to[u], k+1);
    vis[x]=0;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin>>n>>m;
    int u, v;
    for(int i=0;i<m;i++) cin>>u>>v, ins(u, v);
    dfs(1, 1);
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4610.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆