C   74
turn ma
Guest on 11th February 2023 01:26:18 AM


  1. #include<stdio.h>
  2. #define max 200000
  3. int main(){
  4.         int m[105][105], ma[105][105], se[105][105];
  5.         int i, j, k, n, r, c1, c2, d, cnt = 1;
  6.         while(scanf("%d %d", &n, &r) != EOF){
  7.                 for(i=0; i<n; i++){
  8.                         for(j=i; j<n; j++){
  9.                                 m[i][j] = m[j][i] = max;
  10.                                 ma[i][j] = ma[j][i] = 2 * max;
  11.                         }
  12.                 }
  13.                 while(r--){
  14.                         scanf("%d %d %d", &c1, &c2, &d);
  15.                         m[c1][c2] = m[c2][c1] = d;
  16.                 }
  17.                 for(k=0; k<n; k++){
  18.                         for(i=0; i<n; i++){
  19.                                 for(j=i+1; j<n; j++){
  20.                                         if(m[i][k] + m[k][j] < m[i][j]){
  21.                                                 if(m[i][j] < ma[i][j]){
  22.                                                         ma[i][j] = ma[j][i] = m[i][j];
  23.                                                 }
  24.                                                 m[i][j] = m[j][i] = m[i][k] + m[k][j];
  25.                                         }else if(m[i][k] + m[k][j] > m[i][j] && m[i][k] + m[k][j] < ma[i][j]){
  26.                         ma[i][j] = ma[j][i] = m[i][k] + m[k][j];
  27.                                         }
  28.                                         if(m[i][j] < ma[i][k] + m[k][j] && ma[i][k] + m[k][j] < ma[i][j]){
  29.                                             ma[i][j] = ma[j][i] = ma[i][k] + m[k][j];
  30.                                         }
  31.                                         if(m[i][j] < m[i][k] + ma[k][j] && m[i][k] + ma[k][j] < ma[i][j]){
  32.                                                 ma[i][j] = ma[j][i] = m[i][k] + ma[k][j];
  33.                                         }
  34.                                 }
  35.                         }
  36.                        
  37.                 }
  38.                 for(k=0; k<n; k++){
  39.                         for(i=0; i<n; i++){
  40.                                 for(j=i; j<n; j++){
  41.                                         if(i == j){
  42.                         if((2 * m[k][j]) < ma[i][j])
  43.                                                 ma[i][j] = ma[j][i] = (2 * m[k][j]);
  44.                                                 else if((2 * m[k][i]) < ma[i][j])
  45.                                                 ma[i][j] = ma[j][i] = (2 * m[k][i]);
  46.                                         }else{
  47.                                                 if((2 * m[k][j] + m[i][j]) < ma[i][j] && (2 * m[k][j] + m[i][j]) > m[i][j]){
  48.                                                 ma[i][j] = ma[j][i] = (2 * m[k][j] + m[i][j]);
  49.                             /*printf("pass %d =>turn ma[%d][%d] to %d\n", k, i, j, ma[i][j]);*/
  50.                                                 }
  51.                                                 if((2 * m[k][i] + m[i][j]) < ma[i][j] && (2 * m[k][i] + m[i][j]) > m[i][j]){
  52.                                                 ma[i][j] = ma[j][i] = (2 * m[k][i] + m[i][j]);
  53.                                                 /*printf("pass %d =>turn ma[%d][%d] to %d\n", k, i, j, ma[i][j]);*/
  54.                                                 }
  55.                                         }
  56.                                 }
  57.                         }
  58.                 }
  59.                 scanf("%d", &r);
  60.                 printf("Set #%d\n", cnt++);
  61.                 while(r--){
  62.                         scanf("%d %d", &c1, &c2);
  63.                         if(ma[c1][c2] < max)
  64.                             printf("%d\n", ma[c1][c2]);
  65.                         else
  66.                             printf("?\n");
  67.                 }
  68.         }
  69.     return 0;
  70. }
Raw Paste

Login or Register to edit or fork this paste. It's free.