Cod sursa(job #675772)

Utilizator Tase_CCapalna Tanase Tase_C Data 8 februarie 2012 09:37:48
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

fstream fin ("dijkstra.in",ios::in),fout("dijkstra.out",ios::out);

int a,b,c,m[10000][10000],n,i,d[100],v[100],p[100],pmin,j;

int minim(int d[]){
    int i,min,poz=0;
    min=1000;
    for(i=1;i<=n;i++){
       if(!v[i] && d[i]<min){
           min=d[i]; poz=i;
        }
    }
    if(min==1000) return -1;
    v[poz]=1;
    return poz;
}

int main()
{
    int z;
    fin>>n>>z;
    memset(m,20,sizeof(m));
//for(i=1;i<=n;i++){
      while( fin>>a>>b>>c)
      {
       m[a][b]=c;
       m[b][a]=c;
    }
    for(i=1;i<=n;i++)
        m[i][i]=0;
    for(i=2;i<=n;i++){
        d[i]=m[1][i];
        if(d[i]<1000)
            p[i]=1;
    }
   
   
//    for(i=1;i<=n;i++)
 //       fout<<p[i]<<" ";
  //  fout<<endl;
   // for(i=1;i<=n;i++)
    //    fout<<d[i]<<" ";
   
   // fout<<endl;fout<<endl;fout<<endl;fout<<endl;
   
    v[1]=1;
    for(i=1;i<=n-1;i++){
        pmin=minim(d);
  //      fout<<pmin<<endl;
        if(pmin==-1) break;
       
        for(j=2;j<=n;j++){
            //fout<<j<<" "<<d[j]<<" "<<d[pmin]+m[pmin][j]<<endl;
           if(d[j]>d[pmin]+m[pmin][j]){
               d[j]=d[pmin]+m[pmin][j];
               p[j]=pmin;
           }
        }
    }
   // for(i=1;i<=n;i++)
   //     fout<<p[i]<<" ";
 //   fout<<endl;
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}