SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //dijktra
  2. #include<iostream>
  3. #include<fstream>
  4. using namespace std;
  5. typedef unsigned int ui;
  6. ifstream fi("input.inp");
  7. ofstream fo("output.out");
  8.  
  9. ui sum=0;
  10.  
  11. void nhap(ui **&a,ui *&length,ui *&p,bool *&s,ui &n,ui &m,ui &dau,ui &cuoi){
  12.     fi>>n>>m>>dau>>cuoi;dau--;cuoi--;
  13.     ui i,j,u,v;
  14.     a=new ui*[n];length=new ui[n];p=new ui[n];s=new bool[n];
  15.     for(i=0;i<n;i++) a[i]=new ui[n];
  16.     for(i=0;i<n;i++){
  17.         for(j=0;j<n;j++) a[i][j]=0;
  18.     }
  19. //  khoi tao matran va mang
  20.     for(i=0;i<m;i++){
  21.         fi>>u>>v;u--;v--;
  22.         fi>>a[u][v];
  23.  //       a[u][v]=1;a[v][u]=1;
  24.         sum=sum+a[u][v];
  25.     }  
  26.     sum++;
  27.     for(i=0;i<n;i++){
  28.         length[i]=sum;
  29.         p[i]=dau;
  30.         s[i]=true;
  31.         for(j=0;j<n;j++) if(i!=j&&a[i][j]==0) a[i][j]=sum;
  32.     }
  33. /*  for(i=0;i<n;i++){
  34.         for(j=0;j<n;j++) cout<<a[i][j]<<"\t";
  35.         cout<<endl;
  36.     }*/
  37.     length[dau]=0;
  38. }
  39.  
  40. void dijika(ui **a,ui *length,ui *p,bool *s,ui n,ui dau,ui cuoi){
  41.     ui i,j;
  42.     while(s[cuoi]){
  43.         for(i=0;i<n;i++) if(s[i]&&length[i]<sum) break;
  44.         if(i>=n) break;
  45.         for(j=0;j<n;j++) if(s[j]&&length[i]>length[j]) i=j;
  46.         s[i]=false;
  47.         for(j=0;j<n;j++) if(s[j]&&length[j]>a[i][j]+length[i]){
  48.             length[j]=a[i][j]+length[i];
  49.             p[j]=i;
  50.         }
  51.     }
  52. }
  53.  
  54. void xuat(ui i,ui dau,ui *p){
  55.     if(i==dau){
  56.         fo<<i+1<<"\t";
  57.         return;
  58.     }
  59.     xuat(p[i],dau,p);
  60.     fo<<i+1<<"\t";
  61. }
  62.  
  63. int main(){
  64.     ui **a,*length,*p,n,m,dau,cuoi;
  65.     bool *s;
  66.     nhap(a,length,p,s,n,m,dau,cuoi);
  67.     dijika(a,length,p,s,n,dau,cuoi);
  68.     if(length[cuoi]>0&&length[cuoi]<sum){
  69.         fo<<length[cuoi]<<endl;
  70.         xuat(cuoi,dau,p);
  71.     }
  72.     else cout<<"khong tim duoc duong\n";
  73.     fi.close();fo.close();
  74.     delete []s;delete []p;delete []length;
  75.     for(m=0;m<n;m++) delete []a[m];
  76.     delete []a;
  77.     return 0;
  78. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top