fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <limits.h>
  5.  
  6. int N;
  7. int Map[102][102];
  8. int Estimate[102];
  9.  
  10. int main()
  11. {
  12.     int I,J,K;
  13.     char Temp;
  14.     while(EOF!=scanf("%d",&N))
  15.     {
  16.         /*Input*/
  17.         memset(Map,0,4*102*102);
  18.         for (I=2; I<=N; I++)
  19.         {
  20.             for (J=1; J<I-1; J++)
  21.             {
  22.                 scanf("%c",&Temp);
  23.                 if (Temp!='x')
  24.                 {
  25.                     ungetc(Temp,stdin);
  26.                 }
  27.                 else
  28.                 {
  29.                     Map[I][J]=99999999;
  30.                     getchar();
  31.                     continue;
  32.                 }
  33.                 scanf("%d ",&K);
  34.                 Map[I][J]=K;
  35.                 Map[J][I]=K;
  36.             }
  37.             scanf("%c",&Temp);
  38.             if (Temp!='x')
  39.             {
  40.                 ungetc(Temp,stdin);
  41.             }
  42.             else
  43.             {
  44.                 Map[I][J]=99999999;
  45.                 getchar();
  46.                 continue;
  47.             }
  48.             scanf("%d",&K);
  49.             Map[I][J]=K;
  50.             Map[J][I]=K;
  51.         }
  52.  
  53.         /*BellmanFord algorithm*/
  54.         for (I=2;I<=N;I++)
  55.         {
  56.             Estimate[I]=99999999;
  57.         }
  58.         for (I=1;I<=N-1;I++)
  59.         {
  60.             for (J=1;J<=N;J++)
  61.             {
  62.                 for (K=1;K<=N;K++)
  63.                 {
  64.                     if (Map[J][K]>0)
  65.                     {
  66.                         if (Estimate[K]>Estimate[J]+Map[J][K])
  67.                         {
  68.                             Estimate[K]=Estimate[J]+Map[J][K];
  69.                         }
  70.                     }
  71.                 }
  72.             }
  73.         }
  74.  
  75.         /*find the longest path from source*/
  76.         for (I=2,K=Estimate[1];I<=N;I++)
  77.         {
  78.             if (K<Estimate[I])
  79.             {
  80.                 K=Estimate[I];
  81.             }
  82.         }
  83.         printf("%d\n",K);
  84.     }
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0s 2292KB
comments (?)
stdin
copy 
5
50
30 5
100 20 50
10 x x 10
stdout
copy 
35
https://ideone.com/gn7BfF
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!