## 【Codeforces 788C】The Great Mixing

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;
const int M = 2000009;
const int BAS = 1000;

int nxt[M],to[M],_hash[M];
queue<int> que;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
for (int i=1;i<=m;i++) _hash[++tot] = read() - n;
sort(_hash+1, _hash+1+tot);
tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
for (int i=1;i<=tot;i++) {
dis[_hash[i] + BAS] = 1;
que.push(_hash[i] + BAS);
}
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=1,t;t=w+_hash[i],i<=tot;i++) {
if (t < 0 || t > BAS*2 || dis[t]) continue;
dis[t] = dis[w] + 1; que.push(t);
}
}
cout<<(dis[BAS]?dis[BAS]:-1);
return 0;
}


## 【BZOJ 2118】墨墨的等式

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;
const int M = N * 12;
const LL INF = 1e17;

int n,a[N],done[N];
LL dis[N],bmn,bmx,mn=INF;
priority_queue<pair<LL,int> > que;

inline void AddEdge(int u, int v, int c) {
static int E = 1; cost[++E] = c;
}

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Dijkstra() {
for (int i=0;i<mn;i++) dis[i] = INF;
dis[0] = 0; que.push(make_pair(0, 0));
while (!que.empty()) {
int w = que.top().second; que.pop();
if (done[w]) continue; else done[w] = 1;
if (dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i];
que.push(make_pair(-dis[to[i]], to[i]));
}
}
}
}

inline LL cal(LL lim) {
LL ret = 0, tmp;
for (int i=0;i<mn;i++) {
if (lim < dis[i]) continue;
ret += (lim - dis[i]) / mn + 1;
}
return ret;
}

int main() {
for (int i=1;i<=n;i++) {
if (a[i]) mn = min(mn, (LL)a[i]);
}
for (int i=1;i<=n;i++) {
if (a[i] == mn) continue;
for (int j=0;j<mn;j++) {
}
}
Dijkstra();
printf("%lld\n",cal(bmx)-cal(bmn-1));
return 0;
}


## 【BZOJ 4356】[CEOI2014] Wall

### 解题报告

bzoj_4356_solution

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int L = 400 + 9;
const int N = L * L * 4;
const int M = N * 4;
const LL INF = 1e17;

int cx[L][L],cy[L][L],intree[L][L];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
bool del[L][L][4],vis[L][L],done[N],bst[L][L][4];
LL dis[N];
priority_queue<pair<LL, int> > que;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int c) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}

inline int id(int x, int y, int t = 0) {
if (!t) return x + (y - 1) * (n + 1);
else return (x - 1 + (y - 1) * (n + 1) << 2) + t;
}

inline void Dijkstra(int s) {
memset(done, 0, sizeof(done));
fill(dis, dis+N, INF); dis[s] = 0;
que.push(make_pair(0, s));
for (int w;!que.empty();) {
w = que.top().second; que.pop();
if (done[w]) continue;
done[w] = 1;
if (dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i];
que.push(make_pair(-dis[to[i]], to[i]));
}
}
}
}

bool mark(int x, int y, int f) {
if (intree[x][y]) return ~intree[x][y]?1:0;
bool tag = vis[x][y];
if (dis[w] + cost[i] == dis[to[i]] && to[i] != f) {
for (int j=1,nx,ny;j<=4;j++) {
nx = x + dx[j]; ny = y + dy[j];
if (id(nx, ny) == to[i]) {
if (mark(nx, ny, w)) {
bst[x][y][j] = tag = 1;
bst[nx][ny][j+2>4?j-2:j+2] = 1;
}
break;
}
}
}
}
intree[x][y] = tag?1:-1;
return tag;
}

int main() {
del[1][1][2] = del[1][1][4] = 1;
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
vis[i][j] = 1;
del[i][j][4] = 1;
del[i+1][j][3] = 1;
del[i][j+1][1] = 1;
del[i+1][j+1][2] = 1;
}
}
}
for (int j=1,tmp;j<=m;j++) {
for (int i=1;i<=n+1;i++) {
}
}
for (int j=1,tmp;j<=m+1;j++) {
for (int i=1;i<=n;i++) {
}
}
Dijkstra(id(1,1));
mark(1, 1, id(1, 1));
for (int j=1;j<=m+1;j++) {
for (int i=1;i<=n+1;i++) {
if (!del[i][j][1]) {
if (!del[i][j][4] && !bst[i][j][1]) Add_Edge(id(i, j, 1), id(i, j, 4), 0);
if (i <= n && !del[i+1][j][2]) Add_Edge(id(i, j, 1), id(i+1, j, 2), cx[i][j]);
}
if (!del[i][j][2]) {
if (!del[i][j][1] && !bst[i][j][4]) Add_Edge(id(i, j, 2), id(i, j, 1), 0);
if (!del[i][j][3] && !bst[i][j][3]) Add_Edge(id(i, j, 2), id(i, j, 3), 0);
}
if (!del[i][j][3]) {
if (!del[i][j][4] && !bst[i][j][2]) Add_Edge(id(i, j, 3), id(i, j, 4), 0);
if (j <= m && !del[i][j+1][2]) Add_Edge(id(i, j, 3), id(i, j+1, 2), cy[i][j]);
}
if (!del[i][j][4]) {
if (i <= n && !del[i+1][j][3]) Add_Edge(id(i, j, 4), id(i+1, j, 3), cx[i][j]);
if (j <= m && !del[i][j+1][1]) Add_Edge(id(i, j, 4), id(i, j+1, 1), cy[i][j]);
}
}
}
Dijkstra(id(1,1,3));
printf("%lld\n",dis[id(1,1,1)]);
return 0;
}


## 【BZOJ 4383】[POI2015] Pustynia

#### 代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000000;
const int M = 5000000;
const int INF = 1000000000;

int sol[N],vis[N],in[N],n,m,s,bas,tot;
queue<pair<int,int> > leaf;

inline void Add_Edge(int u, int v, int w) {
static int T = 0; in[v]++;
to[++T] = v; nxt[T] = head[u];
head[u] = T; cost[T] = w;
}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

void build(int w, int l, int r) {
bas = max(bas, w);
if (l < r) {
int mid = l + r + 1 >> 1;
Add_Edge(w, w<<1, 0); build(w<<1, l, mid - 1);
Add_Edge(w, w*2+1, 0); build(w*2+1, mid, r);
} else {
leaf.push(make_pair(w,l));
}
}

bool Get_Ans(int w) {
sol[w] = true;
if (vis[to[i]] && val[w] - cost[i] < val[to[i]]) {
return false;
} else {
val[to[i]] = min(val[to[i]], val[w] - cost[i]);
if (--in[to[i]] == 0) {
if (!Get_Ans(to[i])) {
return false;
};
}
}
}
return true;
}

inline bool solve() {
for (int i=1;i<=tot;i++) {
if (!sol[i] && !in[i]) {
if (!Get_Ans(i)) {
return false;
}
}
}
return true;
}

void insert(int w, int l, int r, int L, int R) {
if (L <= l && r <= R) {
} else {
int mid = l + r + 1 >> 1;
if (L < mid) insert(w<<1, l, mid-1, L, R);
if (R >= mid) insert(w*2+1, mid, r, L, R);
}
}

int main(){
build(1,1,n);
while (!leaf.empty()) {
leaf.pop();
}
tot = bas + n;
fill(val, val+N, INF);
for (int i=1,p;i<=s;i++) {
vis[p+bas] = 1;
}

for (int i=1,l,r,k,last;i<=m;i++) {
for (int j=1,tmp;j<=k;j++) {
}
arr[0] = l-1; arr[k+1] = r+1;
for (int j=1;j<=k+1;j++) {
if (arr[j] - arr[j-1] > 1) {
insert(1,1,n,arr[j-1]+1,arr[j]-1);
}
}
}
if (!solve()) {
puts("NIE");
} else {
for (int i=bas;i<=tot;i++) {
if (in[i] || val[i] < 1) {
puts("NIE");
exit(0);
}
}

puts("TAK");
for (int i=1;i<=n;i++)
printf("%d ",val[i+bas]);
}
return 0;
}


## 【Codevs 1817】灾后重建

#include<iostream>
#include<cstdio>
#include<vector>
#define INF 1000099
using namespace std;

struct abc{int point,len;};
int n,m;
int t[299]={0};
int f[299][299];
bool yet[299]={0};
vector<abc> path[299];
bool day[100099]={0};
int pro=0;

void init(){
for (int i=1;i<=250;i++){
t[i]=INF;
}
for (int i=0;i<=250;i++){
for (int j=0;j<=250;j++){
f[i][j]=INF;
}
}
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&t[i]);
if (t[i]==0) yet[i]=true;
}
abc hc;
for (int i=1,a,b,leng;i<=m;i++){
scanf("%d%d%d",&a,&b,&leng);
a++;b++;
f[a][b]=leng;f[b][a]=leng;
hc.point=b;hc.len=leng;
path[a].push_back(hc);
hc.point=a;
path[b].push_back(hc);
}
}

void update(int num){
int end,length;
for (int k=pro+1;k<=end;k++)
yet[k]=true;
for (int k=pro+1;k<=end;k++){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
pro=end;
}

int main(){
int Q,x,y,ti;
init();
cin>>Q;
for (int i=1;i<=Q;i++){
scanf("%d%d%d",&x,&y,&ti);
x++;y++;
if (!day[ti]) {
update(ti);
day[ti]=1;
}
if (f[x][y]<INF && yet[x] && yet[y]) printf("%d\n",f[x][y]);
else printf("-1\n");
}
return 0;
}


## 【UVa 1027】Toll

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 70;
const int M = 2000+9;
const double EPS = 1e-4;

LL d[N]; bool inq[N]; queue<int> que;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline int ID(const char c) {
if ('a' <= c && c <= 'z') return c - 'a' + 1;
else return c - 'A' + 27;
}

inline void Add_Edge(int u, int v) {
}

inline LL cost(int w, LL val) {
if (w == s) return 0;
else if (w <= 26) return 1;
else {
LL l=1,r=1e15,ret=1,mid;
while (l <= r) {
mid = l + r >> 1;
if (val+mid-(LL)(ceil((val+mid)/20.0)+EPS) >= val) ret = mid, r = mid - 1;
else l = mid+1;
}
return ret;
}
}

inline LL SPFA() {
memset(d,0x3f,sizeof(d));
d[t] = MN + (s!=t?cost(t, MN):0);
inq[t] = 1; que.push(t);

while (!que.empty()) {
int w = que.front(); inq[w] = 0; que.pop();
if (d[to[i]] > d[w] + cost(to[i],d[w])) {
d[to[i]] = d[w] + cost(to[i],d[w]);
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return d[s];
}

int main(){
static char U[10],V[10];

for (int i=1;i<=m;i++) {
scanf("%s %s",U+1,V+1);
}

scanf("%s %s",U+1,V+1);
s = ID(U[1]); t = ID(V[1]);
printf("Case %d: %lld\n",++case_cnt,SPFA());
}
return 0;
}


## 【BZOJ 2069】[POI2004] ZAW

1）最短路+奇怪的姿势，时间复杂度O(nlogn)
2）关键点间的最短路，时间复杂度O(nlog^2n)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 50000+9;
const int M = 300000+9;
const int INF = 1e9;

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que; bool vis[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v, int c1, int c2) {
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = c1;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = c2;
}

inline int Dijkstra() {
memset(dis,60,sizeof(dis));
memset(vis,0,sizeof(vis));
que.push(make_pair(0,S));
dis[S] = 0; vis[1] = 1;

while (!que.empty()) {
int w = que.top().second; que.pop();
if (vis[w]) continue;
else vis[w] = 1;
if (dis[to[i]] > dis[w] + cost[i] && !vis[to[i]]) {
dis[to[i]] = dis[w] + cost[i];
que.push(make_pair(dis[to[i]], to[i]));
}
}
}
return dis[T];
}

int main(){
for (int i=1,a,b,c,d;i<=m;i++) {

if (a == 1) {
t1[++tot] = b;
t2[tot] = c;
t3[tot] = d;
} else if (b == 1) {
t1[++tot] = a;
t2[tot] = d;
t3[tot] = c;
}
}

S = N - 1; T = N - 2;
int w = 0, TMP = n, ori = TT;
while (TMP) w++, TMP >>= 1;

for (int k=0,cur=1;k<=w;k++,cur<<=1) {
TT = ori;

for (int i=1;i<=tot;i++) {
}
vout = min(Dijkstra(), vout);

TT = ori;

for (int i=1;i<=tot;i++) {
}
vout = min(Dijkstra(), vout);
}
printf("%d\n",vout);
return 0;
}


## 【NOIP十连测】[D1T3] Walk

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1300000;
const int M = 200000*2+300000+9;

deque<int> que;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v) {
static int T = 0;
}

inline void BFS() {
memset(dis,-1,sizeof(dis));
dis[1] = 0; que.push_back(1);

while (!que.empty()) {
int w = que.front(); que.pop_front();
if (w <= n) {
if (!~dis[to[i]] || dis[to[i]] > dis[w] + 1) dis[to[i]] = dis[w] + 1, que.push_back(to[i]);
} else {
if (!~dis[to[i]] || dis[to[i]] > dis[w]) dis[to[i]] = dis[w], que.push_front(to[i]);
}
if (w > n) for (int i=0;i<=20;i++) if ((w-n)&(1<<i)) {
int v = ((w-n)^(1<<i)) + n; if (v <= n) continue;
if (!~dis[v] || dis[v] > dis[w]) dis[v] = dis[w], que.push_front(v);
}
}
}

int main(){
freopen("walk.in","r",stdin);
freopen("walk.out","w",stdout);
BFS(); for (int i=1;i<=n;i++) printf("%d\n",dis[i]);
return 0;
}


## 【Codeforces 715B】Complete The Graph

1）暴力最短路，复杂度O(nmlogn)

2）神奇二分，复杂度O(mlognlogm)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const LL N = 1000+9;
const LL M = 20000+9;
const LL INF = 1e14;

queue<LL> que;

char c=getchar(); LL ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(LL u, LL v, LL d) {
static LL TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = d;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = d;
}

inline LL SPFA(){
for (int i=1;i<=n;i++) dis[i] = INF;
dis[S] = 0; que.push(S), inq[S] = 1;

while (!que.empty()) {
LL w = que.front(); que.pop(); inq[w] = 0;
for (LL i=head[w];i;i=nxt[i]) if (~cost[i] && dis[to[i]] > dis[w]+cost[i]) {
dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
}
} return dis[T];
}

int main(){
for (LL i=1,tmp;i<=m;i++) {
if (!tmp) tmp = -1, sign[i] = 1;
}
if (SPFA() < L) cout<<"NO", exit(0);
for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = 1;
if ((ty=SPFA()) > L) cout<<"NO", exit(0);
for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = INF;
LL w = T,len_tmp; while (w != S) {if(sign[sur[w]/2]) cost[sur[w]] = cost[sur[w]^1] = 1; w = to[sur[w]^1];}
while ((len_tmp=SPFA()) < L)
for (w=T;w!=S;w=to[sur[w]^1]) if (sign[sur[w]/2]) {
cost[sur[w]] += L - len_tmp, cost[sur[w]^1] += L - len_tmp; break;}
cout<<"YES"<<endl;
for (LL i=1;i<=m;i++)
if (sign[i] && cost[i*2] == -1) printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,L+1);
else printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,cost[i*2]);
return 0;
}