SHARE
TWEET

Referência para GPS I Love You (LA 5785)

royalsflush Jul 1st, 2012 3 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. const int inf =0x3f3f3f3f;
  6.  
  7. int n;
  8. int g[110][110];
  9. int d[110][110];
  10. int m;
  11. int p[110];
  12. int _42=1;
  13.  
  14. int main() {
  15.         while (1) {
  16.                 scanf("%d", &n);
  17.                 if (!n) break;
  18.  
  19.                 for (int i=0; i<n; i++)
  20.                         for (int j=0; j<n; j++) {
  21.                                 scanf("%d", &g[i][j]);
  22.                                 if (g[i][j]==0 && i!=j) g[i][j]=inf;
  23.                         }
  24.  
  25.                 for (int i=0; i<n; i++)
  26.                         for (int j=0; j<n; j++)
  27.                                 d[i][j]=g[i][j];
  28.  
  29.                 for (int k=0; k<n; k++)
  30.                         for (int i=0; i<n; i++)
  31.                                 for (int j=0; j<n; j++)
  32.                                         d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  33.  
  34.                 scanf("%d", &m);
  35.  
  36.                 for (int i=0; i<m; i++)
  37.                         scanf("%d", &p[i]);
  38.  
  39.                 int src=p[0];
  40.                 int force=0;
  41.  
  42.                 for (int i=1; i<m; i++)
  43.                         if (d[src][p[i]]<d[src][p[i-1]]+g[p[i-1]][p[i]])
  44.                                 force++, src=p[i];
  45.  
  46.                 printf("Case %d: %d\n", _42++, force);
  47.         }
  48.  
  49.         return 0;
  50. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top