SHARE
TWEET

Untitled

a guest Apr 26th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. using namespace std;
  5. main(){
  6.     int n,i,j,s,f,inf=1000000;
  7.     cin>>n>>s>>f;int a[n][n];
  8.     for(i=0;i<n;++i)for(j=0;j<n;++j)cin>>a[i][j];
  9.     vector<int>d(n,inf),p(n,s-1);d[s-1]=0;
  10.     priority_queue<pair<int,int> >q;
  11.     q.push({0,s-1});
  12.     while(!q.empty()){
  13.         i=q.top().second;q.pop();
  14.         for(j=0;j<n;++j)
  15.             if(a[i][j]>0 and d[j]>d[i]+a[i][j]){
  16.             d[j]=d[i]+a[i][j];p[j]=i;
  17.             q.push({-d[j],j});}}
  18.     if(d[f-1]<inf){string t=to_string(f);i=f-1;
  19.         while(i!=s-1){i=p[i];t=to_string(i+1)+" "+t;}
  20.         cout<<t;}
  21.     else cout<<-1;}
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
 
Top