2069: [POI2004]ZAW

链接

题意：

　　给定一张带权图（边是双向的，但不同方向长度不同）。求从1出发，至少经过除1外的一个点，再回到1的最短路。点和边不能重复经过。 n≤5000，m≤10000

分析：

　　因为不能重复经过，不能直接最短路的，考虑去掉不能重复经过一个点的限制。

　　可以枚举所有与1有边的点，然后从这里面枚举一个点的，求出到其他与1相连的点最短路，来更新。　

　　这样显然复杂度是关于1的出度的，复杂度并不是很理想。

　　然后这里有一个技巧，按照二进制某一位上的01分成两个集合，然后跑多源最短路。

　　为什么可以呢？任何两个不同的点的二进制位最少存在一位不同。　　

　　复杂度$O(nlog^2n)$

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

#define pa pair<int,int>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = , INF = 1e9;

struct Edge{ int to, nxt, w; } e[];

int head[N], dis[N], df[N], dt[N], A[N], En;

bool vis[N];

priority_queue< pa, vector< pa >, greater< pa > > q;

inline void add_edge(int u,int v,int w) {

    ++En; e[En].to = v, e[En].nxt = head[u], e[En].w = w; head[u] = En;

}

void Dijkstra() {

    while (!q.empty()) {

        int u = q.top().second; q.pop();

        if (vis[u]) continue;

        vis[u] = ;

        for (int i = head[u]; i; i = e[i].nxt) {

            int v = e[i].to;

            if (dis[v] > dis[u] + e[i].w) {

                dis[v] = dis[u] + e[i].w;

                q.push(pa(dis[v], v));

            }

        }

    }

}

int main() {

    int n = read(), m = read(), cnt = ;

    for (int i = ; i <= m; ++i) {

        int u = read(), v = read(), w;

        if (u == ) {

            df[v] = read(), dt[v] = read();

            if (!vis[v]) vis[v] = , A[++cnt] = v;

        }

        else if (v == ) {

            dt[u] = read(), df[u] = read();

            if (!vis[u]) vis[u] = , A[++cnt] = u;

        }

        else {

            w = read();add_edge(u, v, w);

            w = read();add_edge(v, u, w);

        }

    }

    int ans = INF;

    for (int k = ; k <= cnt; k <<= ) {

        for (int i = ; i <= n; ++i) dis[i] = INF, vis[i] = ;

        for (int i = ; i <= cnt; ++i)

            if (i & k) q.push(pa(dis[A[i]] = df[A[i]], A[i]));

        Dijkstra();

        for (int i = ; i <= cnt; ++i)

            if (!(i & k)) ans = min(ans, dis[A[i]] + dt[A[i]]);

        for (int i = ; i <= n; ++i) dis[i] = INF, vis[i] = ;

        for (int i = ; i <= cnt; ++i)

            if (!(i & k)) q.push(pa(dis[A[i]] = df[A[i]], A[i]));

        Dijkstra();

        for (int i = ; i <= cnt; ++i)

            if (i & k) ans = min(ans, dis[A[i]] + dt[A[i]]);

    }

    cout << ans;

    return ;

}