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

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

b07ae917759c4fe0bc399153a5e77318.png

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


9b747bfb293a49ea96171b7d0ecc32f3.png


Code:


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
**/



目录
打赏
0
0
0
0
5
分享
相关文章
PTA 7-2 找奇葩 (20 分)
在一个长度为 n 的正整数序列中,所有的奇数都出现了偶数次,只有一个奇葩奇数出现了奇数次。你的任务就是找出这个奇葩。
161 0
第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?
第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?
200 0
第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?
PTA L1-003 个位数统计(PTA拿下计划1)
PTA L1-003 个位数统计(PTA拿下计划1)
128 0
(数论)蓝桥杯AcWing 1205. 买不到的数目
(数论)蓝桥杯AcWing 1205. 买不到的数目
68 0
AcWing 第 20 场周赛 3995. 最小的和(贪心 优先队列)
AcWing 第 20 场周赛 3995. 最小的和(贪心 优先队列)
143 0
AcWing 第 20 场周赛 3995. 最小的和(贪心 优先队列)
PTA 7-3 拼题 A 是真爱 (20 分)
如果一个人在一段话里很多次提到 pintia,那对拼题 A 就是真爱啦~ 本题就请你检查一下给定的文字中出现了几次 pintia。
186 0
【PTA】龙舌兰酒吧 (BFS求双源最短路)
【PTA】龙舌兰酒吧 (BFS求双源最短路)
201 0
【PTA】龙舌兰酒吧 (BFS求双源最短路)
忆pta水题
本题要求编写程序,先将输入的一系列整数中的最小值与第一个数交换,然后将最大值与最后一个数交换,最后输出交换后的序列。 注意:题目保证最大和最小值都是唯一的。 输入格式: 输入在第一行中给出一个正整数N(≤10),第二行给出N个整数,数字间以空格分隔。 输出格式: 在一行中顺序输出交换后的序列,每个整数后跟一个空格。 输入样例: 5 8 2 5 1 4 结尾无空行 输出样例: 1 2 5 4 8