// 这题是个双倍经验题，另一道是 BZOJ – 4398 福慧双修

（警告：伪证明开始）

#include <bits/stdc++.h>

using namespace std;

int n = 10000, m, N, X[1000000], Y[1000000], A[1000000], B[1000000];

int main(int argc, char const* argv[])
{
N = n >> 1;
for (int i = 1; i <= N; i += 1)
{
X[++m] = 1, Y[m] = 1 + i, A[m] = i, B[m] = 10000;
X[++m] = 1 + i, Y[m] = N + 2, A[m] = 1, B[m] = 10000;
}
for (int i = N + 3; i <= n; i += 1)
X[++m] = i - 1, Y[m] = i, A[m] = B[m] = 1;
while (m < 200000)
X[++m] = n, Y[m] = rand() % N + 2, A[m] = 10000, B[m] = 10000;
printf("%d %d\n", n, m);
for (int i = 1; i <= m; i += 1)
printf("%d %d %d %d\n", X[i], Y[i], A[i], B[i]);
return 0;
}


#include <bits/stdc++.h>

#define NS (10005)
#define MS (400005)

using namespace std;

typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp &dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, m, O[NS], I[NS], Q[NS], ans = INT_MAX;

struct graph
{
int head[NS], nxt[MS], to[MS], w[MS], sz;
inline void push(int a, int b, int c)
{
nxt[sz] = head[a], to[sz] = b, w[sz] = c, head[a] = sz++;
}
inline int operator [] (const int a) const { return to[a]; }
} g;

struct heap
{
PII v[MS];
int sz;
inline PII &operator [] (const int a) { return v[a]; }
inline void push(const PII a)
{
v[sz++] = a, push_heap(v, v + sz, greater<PII>());
}
inline void pop()
{
pop_heap(v, v + sz, greater<PII>()), sz--;
}
} pq;

int dis[NS];

bool book[NS];

void dij(int u)
{
book[u] = 0, pq.push(PII(dis[u], u));
while (pq.sz)
{
int a = pq[0].second; pq.pop();
if (book[a]) continue;
book[a] = 1;
if (I[0] + dis[a] >= ans) continue;
if (a != u && I[a]) ans = min(ans, I[a] + dis[a]);
for (int i = g.head[a]; ~i; i = g.nxt[i])
if (dis[g[i]] > dis[a] + g.w[i])
{
book[g[i]] = 0;
dis[g[i]] = dis[a] + g.w[i];
pq.push(PII(dis[g[i]], g[i]));
}
}
}

inline void run()
{
memset(dis + 1, 127, sizeof(int) * n);
for (int i = 1; i < n; i += 1)
if (O[Q[i]] && dis[Q[i]] > O[Q[i]]) dis[Q[i]] = O[Q[i]], dij(Q[i]);
}

int main(int argc, char const* argv[])
{
srand(19260817), IN(n), IN(m);
for (int i = 1, a, b, c, d; i <= m; i += 1)
{
IN(a), IN(b), IN(c), IN(d);
if (a > b) swap(a, b), swap(c, d);
if (a == 1)
{
if (O[b])
{
ans = min(ans, min(O[b] + d, c + I[b]));
O[b] = min(O[b], c), I[b] = min(I[b], d);
}
else O[b] = c, I[b] = d;
I[0] = min(I[0], I[b]);
}
else g.push(a, b, c), g.push(b, a, d);
}
for (int i = 2; i <= n; i += 1) Q[i - 1] = i;
random_shuffle(Q + 1, Q + n);
run(), reverse(Q + 1, Q + n), run();
printf("%d\n", ans);
return 0;
}


psb 同学考场写了个只加了 $dis \geq ans$就 continue 的优化也 AC 了，于是就被我针对了。

#include <bits/stdc++.h>

using namespace std;

int n = 9001, m, N = 1000, p = 1, cnt = 1;

int X[1000000], Y[1000000], A[1000000], B[1000000];

int main(int argc, char const* argv[])
{
srand(time(0));
int psb = rand() % N + 1;
for(int i = 1; i <= N; i += 1)
X[++m] = 1, Y[m] = ++p, A[m] = 2 - (i == psb), B[m] = 10000;
while (n - p >= N)
{
for(int i = 1; i <= N; i += 1)
p++, X[++m] = p - N, Y[m] = p, A[m] = 1, B[m] = 10000;
for(int i = 1; i < N; i += 1)
X[++m] = p - i, Y[m] = p, A[m] = p - i, B[m] = p - i + 1;
}
printf("%d %d\n", n, m);
for (int i = 1; i <= m; i += 1)
printf("%d %d %d %d\n", X[i], Y[i], A[i], B[i]);
return 0;
}


#### Remmina

No puzzle that couldn't be solved.