fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define INF 99999999
  3.  
  4. using namespace std;
  5.  
  6. int graph[105][105];
  7.  
  8. void init()
  9. {
  10.     for(int i=1; i<=102; i++)
  11.     {
  12.         for(int j=1; j<=102; j++)
  13.         {
  14.             if(i==j)
  15.                 graph[i][j] = 0;
  16.             else
  17.                 graph[i][j] = INF;
  18.         }
  19.     }
  20. }
  21.  
  22. int main()
  23. {
  24.     int test;
  25.     scanf("%d", &test);
  26.     for(int cs = 1; cs<=test; cs++)
  27.     {
  28.         init();
  29.         int node, edge, u, v, cost;
  30.         scanf("%d %d", &node, &edge);
  31.         for(int i=0; i<edge; i++)
  32.         {
  33.             scanf("%d %d %d", &u, &v, &cost);
  34.             graph[u][v] = graph[v][u] = min(cost, graph[u][v]);
  35.         }
  36.         for(int k=1; k<=node; k++)
  37.         {
  38.             for(int i=1; i<=node; i++)
  39.             {
  40.                 for(int j=1; j<=node; j++)
  41.                 {
  42.                     graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
  43.                 }
  44.             }
  45.         }
  46.         /*for(int i=1; i<=node; i++)
  47.         {
  48.             for(int j=1; j<=node; j++)
  49.             {
  50.                 printf("%d ", graph[i][j]);
  51.             }
  52.             printf("\n");
  53.         }*/
  54.         int cntdup = 0, mindis = INF, mini = INF;
  55.         bool in;
  56.         for(int i=6; i<=node; i++)
  57.         {
  58.             bool all = true;
  59.             in = false;
  60.             int nodecnt = 0, maxi = 0;
  61.             if( graph[i][1]<INF && graph[i][1]==graph[i][2] && graph[i][2]==graph[i][3]
  62.                 && graph[i][3]==graph[i][4] && graph[i][4]==graph[i][5])
  63.             {
  64.                 nodecnt = nodecnt + 5;
  65.                 mindis = min(mindis, graph[i][1]);
  66.                 in = true;
  67.             }
  68.             if(in)
  69.             {
  70.                 for(int j = 6; j<=node && in; j++)
  71.                 {
  72.                     if(graph[i][j]<INF)
  73.                     {
  74.                         maxi = max(maxi, graph[i][j]);
  75.                         nodecnt++;
  76.                     }
  77.                 }
  78.                 //cout<<"Node "<<i<<"= "<<maxi<<endl;
  79.                 if(nodecnt==node)
  80.                 {
  81.                     if(in)cntdup++;
  82.                     mini = min(mini, maxi);
  83.                 }
  84.             }
  85.         }
  86.         if(cntdup==1) printf("Map %d: %d\n", cs, mindis);
  87.         else if(cntdup>1) printf("Map %d: %d\n", cs, mini);
  88.         else printf("Map %d: %d\n", cs, -1);
  89.  
  90.     }
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
5
7 11
1 7 2
2 7 2
3 7 2
5 7 2
6 7 1
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1
7 6 1
6 1
1 2 3
7 5
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1
10 17
1 9 20
1 7 12
2 3 7
2 8 10
2 7 12
3 8 10
4 8 10
4 6 4
5 7 12
5 9 20
5 9 31
6 9 16
6 10 35
7 8 2
7 9 35
8 9 10
9 10 40
6 5
1 6 10
2 6 10
3 6 10
4 6 10
5 6 10
stdout
copy 
Map 1: 1
Map 2: -1
Map 3: -1
Map 4: 40
Map 5: 10
https://ideone.com/ZRGBBr
language:
C++14 (gcc 8.3)
created:
9 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!