BZOJ 2118 墨墨的等式

模意义下最短路

挂题解 http://blog.csdn.net/PoPoQQQ/article/details/46605701

#include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define N 500005 #define M 14 using namespace std; namespace runzhe2000 { typedef long long ll; const ll INF = 1ll<<60; ll dis[N], Bmin, Bmax; bool inq[N]; int ecnt, n, last[N], a[M]; struct edge{int next, to, val;}e[N*M]; void addedge(int a, int b, int c) { e[++ecnt] = (edge){last[a], b, c}; last[a] = ecnt; } void SPFA() { queue<int> q; q.push(0); for(int i = 0; i < a[1]; i++) dis[i] = INF; dis[0] = 0; for(; !q.empty(); q.pop()) { int x = q.front(); inq[x] = 0; for(int i = last[x]; i; i = e[i].next) { int y = e[i].to; if(dis[x] + e[i].val < dis[y]) { dis[y] = dis[x] + e[i].val; if(!inq[y])q.push(y), inq[y] = 1; } } } } ll calc(ll lim, ll a, int b) // 干，没注意到a也要看long long，调了好一会儿 { if(lim < a) return 0; else return (lim - a) / b + 1; } void main() { scanf("%d%lld%lld",&n,&Bmin,&Bmax); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); if(!a[i]){i--; n--; continue;} } sort(a+1, a+1+n); for(int i = 0; i < a[1]; i++) for(int j = 2; j <= n; j++) addedge(i, (i+a[j])%a[1], a[j]); SPFA(); ll ans = 0; for(int i = 0; i < a[1]; i++) { if(dis[i] == INF) continue; ans += calc(Bmax, dis[i], a[1]); ans -= calc(Bmin-1, dis[i], a[1]); } PRintf("%lld\n",ans); } } int main() { runzhe2000::main(); }