fork download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define MAX 10005
  6. #define Node pair< int , int > 
  7. #define INF 1<<30
  8.  
  9. struct cmp {
  10.     bool operator() ( const Node &a , const Node &b ) {
  11.         return a.second > b.second;
  12.     }
  13. };
  14. vector< Node > ady[ MAX ]; vector<int> distancia[ MAX ]; 
  15. bool visitado[ MAX ];  
  16. priority_queue< Node , vector<Node> , cmp > Q; 
  17. int V;                 
  18.  void init(){
  19.     for( int i = 0 ; i <= V ; ++i ){
  20.        for (int j = 0; j <= V; ++j)
  21.        {
  22.         distancia[i].push_back(INF);  
  23.        }
  24.         visitado[ i ] = false; 
  25.     }
  26. }
  27.  
  28. void relajacion( int actual , int adyacente , int peso ,int inicial){
  29.  
  30.     if( distancia[ inicial ][actual] + peso < distancia[ inicial][adyacente ] ){
  31.         distancia[ inicial][adyacente ] = distancia[ inicial ][actual] + peso;   
  32.         Q.push( Node( adyacente , distancia[inicial][ adyacente ] ) ); 
  33.     }
  34. }
  35.  
  36.  
  37.  
  38. void dijkstra( int inicial ){
  39.     init(); 
  40.     Q.push( Node( inicial , 0 ) ); 
  41.     distancia[ inicial ][inicial]=0;     
  42.     int actual , adyacente , peso;
  43.     while( !Q.empty() ){                  
  44.         actual = Q.top().first;           
  45.         Q.pop();                           
  46.         if( visitado[ actual ] ) continue;  
  47.         visitado[ actual ] = true;        
  48.  
  49.         for( int i = 0 ; i < ady[ actual ].size() ; ++i ){ 
  50.             adyacente = ady[ actual ][ i ].first; 
  51.             peso = ady[ actual ][ i ].second;      
  52.             if( !visitado[ adyacente ] ){       
  53.                 relajacion( actual , adyacente , peso ,inicial);
  54.             }
  55.         }
  56.     }
  57.  
  58.  
  59. }
  60.  
  61.  
  62. int main(){
  63.     int  origen, destino , peso , inicial;
  64.     int f;
  65.     while(cin>>f>>V){
  66.     vector <int> fire(f);
  67.     for(int i=0;i<f;i++){
  68.         scanf("%d",&fire[i]);
  69.     }
  70.  
  71.  
  72.     for (int i = 0; i < V; ++i)
  73.     {
  74.         scanf("%d %d %d" , &origen , &destino , &peso );
  75.         ady[ origen ].push_back( Node( destino , peso ) ); 
  76.         ady[ destino ].push_back( Node( origen, peso ) );   }
  77.  
  78.     for (int i = 1; i <= V; ++i)
  79.     {
  80.         dijkstra(i);
  81.     }
  82.     int consulta=0;
  83.             int cont2=INF;
  84.  
  85.     for (int i = 1; i <= V; ++i)
  86.     {   
  87.         int cont=0;
  88.         int nuevo=INF;
  89.         fire.push_back(i);
  90.  
  91.         for (int k = 1; k <= V; ++k)
  92.         {
  93.             nuevo=INF;
  94.             vector<int>::iterator it=find(fire.begin(),fire.end(),k);
  95.             if(it!=fire.end())continue;
  96.             for (int j = 0; j < fire.size(); ++j)
  97.             {
  98.                 if(k!=fire[j]){
  99.                     if(nuevo>distancia[k][fire[j]]){
  100.                         nuevo=distancia[k][fire[j]];
  101.                     }
  102.             } 
  103.  
  104.             }   
  105.             if(nuevo==INF){
  106.                 nuevo=0;
  107.             }
  108.             cont+=nuevo;
  109.         }
  110.  
  111.          if(cont2>cont){
  112.             cont2=cont;
  113.             consulta=i;
  114.          }
  115.       fire.pop_back();
  116.     }
  117.     printf("%d",consulta);
  118.     return 0;
  119. }
  120. }
  121.  
  122.  
  123.  
Success #stdin #stdout 0s 3708KB
comments (?)
stdin
copy 
1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10
stdout
copy 
5
https://ideone.com/b5k2Jc
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!