Algoritmo: Ajudando a prefeitura « Sippert, Tiago A. S.

Algoritmo: Ajudando a prefeitura

Posted by sippert | Filed under algoritmos

Algoritmo de Maratona de Programção utilizando Grafo

#include<iostream>
const int INF = 100;
using namespace std;
int main(){
  int n,m,q,t=1;
  cout.setf(ios::fixed);
  cout.precision(3);
  while((cin>>n>>m)&&(n!=0)&&(m!=0)){
   double M[n][n];
   memset(M,INF,sizeof(M));
   for(int i=0;i<n;i++)M[i][i]=0;
   for(int i=0;i<m;i++){
     int u,v;
     double p;
     cin >> u >> v >> p;
     M[u][v]=p;
     M[v][u]=p;
   }
  for(int k=0; k<n; k++)
    for(int i=0; i<n; i++)
      if( i!=k && M[i][k]<INF )
        for(int j=0; j<n; j++)
          if(M[i][j] > M[i][k]+(100-M[i][k])*(M[k][j]/100))
            M[i][j] = M[i][k]+(100-M[i][k])*(M[k][j]/100);
    cin >> q;
    cout << "Instancia " << t++ << endl;
    for(int i=0;i<q;i++){
      int a,b;
      cin >> a >> b;
      cout << ((double)((int)(M[a][b]*1000)))/1000 << endl;
    }
    cout << endl;
  }
  return 0;
}

Compartilhe: