CF挂0了，简直碉堡了。两道题都是正确的思路但是写残了。写个解题报告记录一下心路历程。
A题问的是 一个n*m的方块的矩形上切k刀，最小的那一块最大可以是多少。不难发现如果纵向切k1刀，横向切k2刀，那么答案应该是 (n/(k1+1)) * (m/(k2+1)),除法是取整的。虽然是取整，但是不难发现其实就是要(k1+1)*(k2+1)最小，根据均值不等式，k1+k2=k(定值) k1==k2的时候(k1+1)*(k2+1)＝k1*k2+k1+k2+1=k1*k2+k+1应该是取最大值，所以当k1,k2越接近两端的时候这个值才会最小，所以我们总是先把某一维的切掉，然后再考虑剩下那一维。比赛的时候手残写错了，哎。。。
B题问的是给你一个图，一些是普通边，一些是train route边，train route边是从首都1连到其它点的，问的是train route边最多可以去掉多少条使得每个点的最短路径长不变。思路就是如果某个点我们可以通过走别的点到达的话，那么这条边是不需要的，留边的时候更新ans我写漏了，导致答案小了很多。
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std; #define ll long long
#define maxn 105000
#define inf 10000000000000000LL int n, m, k; struct Edge
{
int v;
ll w;
Edge(int vi, ll wi) : v(vi), w(wi){}
Edge(){}
}; vector<Edge>G[maxn];
ll dis2[maxn];
ll ans = 0; ll d[maxn];
bool in[maxn];
void spfa()
{
memset(d, 0x3f, sizeof(d));
memset(in, 0, sizeof(in));
queue<int> que;
que.push(1); in[1] = true;
d[1] = 0;
while (!que.empty()){
int u = que.front(); que.pop(); in[u] = false;
for (int i = 0; i < G[u].size(); i++){
int v = G[u][i].v; ll w = G[u][i].w;
if (d[u] + w < d[v]){
d[v] = d[u] + w;
if (!in[v]) que.push(v), in[v] = true;
}
}
}
} ll d2[maxn];
bool upd[maxn]; void spfa2()
{
memset(d2, 0x3f, sizeof(d2));
memset(in, 0, sizeof(in));
queue<int> que;
que.push(1); d2[1] = 0; in[1] = true;
for (int i = 2; i <= n; i++){
if (dis2[i] < d[i]){
que.push(i); in[i] = true; d2[i] = dis2[i];
}
}
while (!que.empty()){
int u = que.front(); que.pop(); in[u] = false;
for (int i = 0; i < G[u].size(); i++){
int v = G[u][i].v; ll w = G[u][i].w;
if (d2[u] + w < d2[v]){
d2[v] = d2[u] + w;
if (!in[v]) que.push(v), in[v] = true;
if (upd[v]) {
++ans; upd[v] = false;
}
}
else if (d2[u] + w == d2[v]){
if (upd[v]) {
++ans; upd[v] = false;
}
}
}
}
} int main()
{
while (cin >> n >> m >> k){
for (int i = 0; i <= n; i++) G[i].clear();
memset(dis2, 0x3f, sizeof(dis2));
ans = 0;
int ui, vi; ll wi;
for (int i = 0; i < m; i++){
scanf("%d%d%I64d", &ui, &vi, &wi);
G[ui].push_back(Edge(vi, wi));
G[vi].push_back(Edge(ui, wi));
}
spfa();
memcpy(dis2, d, sizeof(dis2));
memset(upd, 0, sizeof(upd));
int si; ll yi;
for (int i = 0; i < k; i++){
scanf("%d%I64d", &si, &yi);
if (dis2[si] <= yi) ++ans;
else {
dis2[si] = yi;
if (upd[si]) {
++ans;
}
upd[si] = true;
}
}
spfa2();
cout << ans << endl;
}
return 0;
}