PTA 森森旅游 (30 分) | 堆优化迪杰斯特拉

6 11 3
1 2 3 5
1 3 8 4
2 4 4 6
3 1 8 6
1 3 10 8
2 3 2 8
3 4 5 3
3 5 10 7
3 3 2 3
4 6 10 12
5 6 10 6
3 4 5 2 5 100
1 2
2 1
1 17

8
8
1

typedef pair<long long, int> PII;
int n, m, q;
int head1[maxn], head2[maxn];
ll dis1[maxn], dis2[maxn];
struct node {
  int v, to, nex;
  int w;
}e[maxn << 2];
int idx;
multiset<ll> mst;
void init() {
  idx = 0;
  memset(head1, -1, sizeof head1);
  memset(head2, -1, sizeof head2);
}
void add(int h[], int u, int v, int w) {
  e[idx].v = v;
  e[idx].nex = h[u];
  e[idx].w = w;
  h[u] = idx++;
}
bool vis[maxn];
void dij(ll dis[], int head[], int st) {
  memset(dis, 0x3f3f3f3f3f3f3f3f, sizeof dis1);
  memset(vis, 0, sizeof vis);
  priority_queue <PII, vector<PII>, greater<PII> > que;
  que.push({ 0,st });
  dis[st] = 0;
  while (que.size()) {
    int u = que.top().second;
    que.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = head[u]; ~i; i = e[i].nex) {
      //  cout << e[i].v << endl;
      int to = e[i].v;
      if (dis[to] > dis[u] + e[i].w) {
        dis[to] = dis[u] + e[i].w;
        que.push({ dis[to],to });
      }
    }
  }
}
int a[maxn];
void getAns() {
  for (int i = 1; i <= n; i++) {
    if (dis1[i] == 0x3f3f3f3f3f3f3f3f) continue;
    if (dis2[i] == 0x3f3f3f3f3f3f3f3f) continue;
    ll val = dis1[i] + (dis2[i] + a[i] - 1) / a[i];
    mst.insert(val);
    // puts("add");
  }
  for (int qq = 1; qq <= q; qq++) {
    //  puts("qq");
    int x = read, aa = read;
    if (dis1[x] != 0x3f3f3f3f3f3f3f3f && dis2[x] != 0x3f3f3f3f3f3f3f3f) {
      ll t = dis1[x] + (dis2[x] + a[x] - 1) / a[x];
      mst.erase(mst.find(t));
      a[x] = aa;
      ll val = dis1[x] + (dis2[x] + aa - 1) / aa;
      mst.insert(val);
    }
    printf("%lld\n", *mst.begin());
  }
}
int main() {
  n = read, m = read, q = read;
  init();
  memset(dis1, 0x3f3f3f3f3f3f3f3f, sizeof dis1);
  memset(dis2, 0x3f3f3f3f3f3f3f3f, sizeof dis2);
  for (int i = 1; i <= m; i++) {
    int u = read, v = read, c = read, d = read;
    add(head1, u, v, c);
    add(head2, v, u, d);
  }
  for (int i = 1; i <= n; i++) a[i] = read;
  dij(dis1, head1, 1);
  dij(dis2, head2, n);
  /*
  for (int i = 1; i <= n; i++) {
    cout << dis1[i] << " " << dis2[i] << endl;
  }*/
  getAns();
  return 0;
}
/**
6 11 3
1 2 3 5
1 3 8 4
2 4 4 6
3 1 8 6
1 3 10 8
2 3 2 8
3 4 5 3
3 5 10 7
3 3 2 3
4 6 10 12
5 6 10 6
3 4 5 2 5 100
1 2
2 1
1 17
**/