YEZAELP

TOI17: 1221

Jan 3rd, 2022 (edited)
232
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int inf = 1e9;
  5. const int N = 5e2 + 10;
  6. int ar[N], dis[N][N], cnt[N][N];
  7.  
  8. int main(){
  9.  
  10.     int n, m, Q;
  11.     scanf("%d %d %d", &n, &m, &Q);
  12.  
  13.     for(int i=1;i<=n;i++)
  14.         scanf("%d", &ar[i]);
  15.  
  16.     for(int i=1;i<=n;i++){
  17.         for(int j=1;j<=n;j++){
  18.             if(i == j) dis[i][j] = 0;
  19.             else dis[i][j] = ar[i] + ar[j],
  20.                  cnt[i][j] = 1 + 1;
  21.         }
  22.     }
  23.  
  24.     for(int i=1;i<=m;i++){
  25.         int u, v, w;
  26.         scanf("%d %d %d", &u, &v, &w);
  27.         if(w < dis[u][v]) dis[u][v] = dis[v][u] = w,
  28.                           cnt[u][v] = cnt[v][u] = 1 + 1;
  29.     }
  30.  
  31.     for(int k=1;k<=n;k++){
  32.         for(int u=1;u<=n;u++){
  33.             for(int v=1;v<=n;v++){
  34.                 int sum_dis = dis[u][k] + dis[k][v];
  35.                 int sum_cnt = cnt[u][k] + cnt[k][v];
  36.                 if(sum_dis < dis[u][v])
  37.                     dis[u][v] = dis[v][u] = sum_dis,
  38.                     cnt[u][v] = cnt[v][u] = sum_cnt;
  39.                 else if(sum_dis == dis[u][v])
  40.                     cnt[u][v] = cnt[v][u] = max(cnt[u][v], sum_cnt);
  41.             }
  42.         }
  43.     }
  44.  
  45.     for(int q=1;q<=Q;q++){
  46.         int u, v;
  47.         scanf("%d %d", &u, &v);
  48.         printf("%d %d\n", dis[u][v], cnt[u][v]);
  49.     }
  50.  
  51.     return 0;
  52. }
RAW Paste Data Copied