SHARE
TWEET

Instant View Of Big Bang Uva

ee1150439 Jul 1st, 2017 30 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int t;
  5.     cin>>t;
  6.     for(int a=1;a<=t;a++){
  7.         int n,m;
  8.         vector<pair<int,int> >out[1001];
  9.         vector<int>in[1001];
  10.         cin>>n>>m;
  11.         int x,y,t;
  12.         vector<int>v;
  13.         for(int i=0;i<m;i++){
  14.             cin>>x>>y>>t;
  15.             out[x+1].push_back(make_pair(y+1,t));
  16.             in[y+1].push_back(x+1);
  17.         }
  18.         for(int i=0;i<n;i++){
  19.             out[0].push_back(make_pair(i+1,0));
  20.             in[i+1].push_back(0);
  21.         }
  22.         int dist[1001];
  23.         for(int i=1;i<=n;i++)dist[i] = INT_MAX;
  24.         dist[0]=0;
  25.         bool f =false;
  26.         for(int i=0;i<n;i++){
  27.             bool flag = false;
  28.             for(int j=0;j<=n;j++){
  29.                 for(int k=0;k<out[j].size();k++){
  30.                     if(dist[out[j][k].first]>dist[j]+out[j][k].second){
  31.                         flag = true;
  32.                         dist[out[j][k].first] = dist[j]+out[j][k].second;
  33.                     }
  34.                 }
  35.             }
  36.             if(!flag){
  37.                 cout<<"Case "<<a<<": impossible"<<endl;
  38.                 f =true;
  39.                 break;
  40.             }
  41.         }
  42.         if(f)continue;
  43.         int source =-1;
  44.         for(int j=0;j<=n;j++){
  45.             for(int k=0;k<out[j].size();k++){
  46.                 int u = out[j][k].first;
  47.                 int weight = out[j][k].second;
  48.         //      cout<<u<<" "<<dist[u]<<" "<<j<<" "<<dist[j]+weight<<endl;
  49.                 if(dist[u]>dist[j]+weight){
  50.                     source = u;
  51.                     break;
  52.                 }
  53.             }
  54.             if(source!=-1)break;
  55.         }
  56.         if(source==-1){
  57.             cout<<"Case "<<a<<": impossible"<<endl;
  58.             continue;
  59.         }
  60.         bool visited[1001];
  61.         for(int i=0;i<=n;i++)visited[i] = false;
  62.         queue<int>q;
  63.         q.push(source);
  64.         while(!q.empty()){
  65.             int u   = q.front();
  66.             visited[u] = true;
  67.             q.pop();
  68.             v.push_back(u);
  69.             for(int i=0;i<in[u].size();i++){
  70.                 if(!visited[in[u][i]] && in[u][i]!=0){
  71.                     q.push(in[u][i]);
  72.                 }
  73.             }  
  74.         }
  75.         sort(v.begin(),v.end());
  76.         cout<<"Case "<<a<<": ";
  77.         for(int i=0;i<v.size();i++){
  78.             if(i==0)cout<<v[i]-1;
  79.             else cout<<" "<<v[i]-1;
  80.         }
  81.         cout<<endl;
  82.     }
  83. }
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