spfa SLF+LLL 32pts

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

int n, m;
int a[10005][10005];
const int N = 1e5 + 5;
struct node
{
	int v, w;
};
vector<node> g[N];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}, dist[N], s[N], t[N];
int id(int x, int y){return (x - 1) * m + y;}
bool vis[N];
void spfa(int s)
{
	deque<int> q;
	q.push_front(s);
	memset(vis, 0, sizeof(vis));	
	memset(dist, 0x3f, sizeof(dist));
	dist[s] = 0;
	vis[s] = 1;
	double sum = 0; int cnt = 1;
	while(q.size()){
		int u = q.front(); q.pop_front();
		if(cnt * dist[u] > sum){
			q.push_back(u);
			continue;
		}
		sum -= dist[u]; cnt -- ;
		vis[u] = 0;
		for(int i = 0;i < g[u].size();i ++ ){
			int v = g[u][i].v, w = g[u][i].w;
			if(dist[v] > dist[u] + w){
				dist[v] = dist[u] + w;
				if(!vis[v]){
					vis[v] = 1;
					sum += dist[v]; cnt ++ ;
					if(q.size() && dist[v] < dist[q.front()]) q.push_front(v);
					else q.push_back(v);
					// q.push(v);
				}
			}
		}
	}
}
signed main()
{
	int q;
	cin >> n >> m >> q;
	for(int i = 1;i <= n;i ++ ){
		for(int j = 1;j <= m;j ++ ){
			cin >> a[i][j];
		}
	}
	for(int i = 1;i <= n;i ++ ){
		for(int j = 1;j <= m;j ++ ){
			for(int k = 0;k < 4;k ++ ){
				int nx = i + dx[k], ny = j + dy[k];
				if(nx >= 1 && nx <= n && ny >= 1 && ny <= m){
					g[id(i, j)].push_back({id(nx, ny), a[i][j]});
				}
				if(a[i][j] + a[nx][ny] < 0 && nx >= 1 && nx <= n && ny >= 1 && ny <= m){
					// cout << a[i][j] << ' ' << a[nx][ny] << endl;
					puts("No");
					return 0;
				}
			}
		}
	}
	for(int i = 1;i <= q;i ++ ) cin >> s[i] >> t[i];
	int ans = LONG_LONG_MAX;
	for(int i = 1;i <= n * m;i ++ ){
		spfa(i);
		int maxn = LONG_LONG_MIN;
		for(int j = 1;j <= q;j ++ ){
			maxn = max(maxn, dist[id(s[j], t[j])] + a[s[j]][t[j]]);
		}
		ans = min(ans, maxn);
	}
	cout << ans << endl;
	return 0;
}