Solution of UVa 821 Page Hopping

/* Bismillahir Rahmanir Rahim Solution-Using "Floyd Warshall" */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) #define ll long long using namespace std; set<ll>st; ll dis[101][101]; int main(){ ll n, e, u, v, w, cs=1, mx, sum, sz; float ans; while(1){ mx=0, sum=0; for(ll i=1; i<=100; i++){ for(ll j=1; j<=100; j++){ if(i==j)dis[i][j]=0; else dis[i][j]=1000000009; } } cin>>u>>v; if(u==0&&v==0) break; else{ st.insert(u); st.insert(v); mx=max(mx, max(u, v)); dis[u][v]=1; while(1){ cin>>u>>v; if(u==0&&v==0) break; else{ st.insert(u); st.insert(v); mx=max(mx, max(u, v)); dis[u][v]=1; } } } for(ll k=1; k<=mx; k++){ for(ll i=1; i<=mx; i++){ for(ll j=1; j<=mx; j++){ dis[i][j]=min(dis[i][j], (dis[i][k]+dis[k][j])); } } } for(ll i=1; i<=mx; i++){ for(ll j=1; j<=mx; j++){ if(dis[i][j]!=1000000009) sum=sum+dis[i][j]; } } sz=st.size(); sz=sz*(sz-1); ans=(double)sum/sz; cout<<"Case "<<cs++<<": average length between pages = "; printf("%.3f clicks\n", ans); st.clear(); } return 0; }

Solution of UVa 11015 - 05-2 Rendezvous

/* Bismillahir Rahmanir Rahim Solution-Using "Floyd Warshall" */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) using namespace std; int main(){ int cs=1, n, u, v, w, m; string s; while(1){ int i, j, k, dis[25][25], ans, sum, mn=1000000009; map<int, string>mp; cin>>n>>m; if(n==0) break; fi(1, n){ cin>>s; mp[i]=s; } for(i=1; i<=n; i++){ for(j=1; j<=n; j++){ if(i==j)dis[i][j]=0; else dis[i][j]=1000000009; } } fi(0, m-1){ cin>>u>>v>>w; dis[u][v]=dis[v][u]=w; } for(k=1; k<=n; k++){ for(i=1; i<=n; i++){ for(j=1; j<=n; j++){ dis[i][j]=min(dis[i][j], (dis[i][k]+dis[k][j])); } } } for(i=1; i<=n; i++){ sum=0; for(j=1; j<=n; j++){ sum=sum+dis[i][j]; } if(mn>sum){ mn=sum; ans=i; } } cout<<"Case #"<<cs++<<" : "<<mp[ans]<<endl; } return 0; }

Floyd Warshal Especial Case

Floyd Warshall Algorithm Various Cases: 

যদি n সংখ্যক নোড থাকে এবং এদের মধ্যকার পাথগুলো দেওয়া থাকে  এবং পরে এক একটা নোড দেবে আর এখন পর্যান্ত "All pair shortest path" বের করতে বলবে। এই রকম হলে,
স্বাভাবিকভাবে input নিতে হবে এবং Floyd Warshall প্রয়োগ করতে হবে। তবে k (মাঝের নোডটি) এর মান শুধুমাত্র যে নোডগুলো এখন পর্যান্ত নেওয়া হয়েছে সেগুলো নিতে হবে। কাজ শেষ, এখন পর্যান্ত নেওয়া নোডগুলোর মধ্যকার "All pair shortest path" বের করা হয়ে গেছে। Code দেখলে পরিস্কার হবে। আর Codeforces 295B এর solution এই ভাবেই হবে (Just reverse).

/* Bismillahir Rahmanir Rahim Solution using "Floyd Warshall" */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) #define fii(i, n, m) for(int i=n; i<=m; i++) #define fdi(i, n, m) for(int i=n; i>=m; i--) using namespace std; long long ar[505][505], ans[505], q[505], n; int main(){ cin>>n; fii(i, 1, n){ fii(j, 1, n){ cin>>ar[i][j]; } } fi(1, n) cin>>q[i]; fdi(k, n, 1){ // Calculating the ans reversely fii(i, 1, n){ fii(j, 1, n){ /*Here is the main task*/ ar[i][j]=min(ar[i][j], (ar[i][q[k]]+ar[q[k]][j])); } } ans[k]=0; fii(i, k, n){ fii(j, k, n){ /*Just saving the answer*/ ans[k]=ans[k]+ar[q[i]][q[j]]; } } } fi(1, n) cout<<ans[i]<<" "; cout<<endl; return 0; }

Solution of 10246 Asterix and Obelix

"All pair shortest path" বের করার সময় শুধুমাত্র path এর cost দেওয়া থাকে আর তার উপর ভিত্তি করে ans বের করতে হয়। কিন্তু এখানে শুধু path এর cost না, সাথে সেই path এর maximum node cost নিবে । অর্থাৎ two dimensional purpose। এই ক্ষেত্রে দুইবার Floyd Warshall প্রয়োগ করতে হবে। 

/* Bismillahir Rahmanir Rahim Just apply "Floyd Warshall" algorithm two times */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=ml i--) #define inf 100000000 using namespace std; int main(){ int cs=1, n, m, r, u, v, w, q, tcost; while(1){ int total, x, dis[90][90], c[90][90]; cin>>n>>m>>q; if(n==0&&m==0&&q==0) break; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(i==j) dis[i][j]=0; else dis[i][j]=inf; c[i][j]=inf; } } fi(1, n){ cin>>x; c[i][i]=x; } fi(1, m){ cin>>u>>v>>w; dis[u][v]=w; dis[v][u]=w; c[u][v]=c[v][u]=max(c[u][u], c[v][v]); } for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ total=dis[i][k]+dis[k][j]; tcost=max(c[i][k], c[k][j]); if(dis[i][j]+c[i][j]>total+tcost){ dis[i][j]=total; c[i][j]=tcost; } } } } for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ total=dis[i][k]+dis[k][j]; tcost=max(c[i][k], c[k][j]); if(dis[i][j]+c[i][j]>total+tcost){ dis[i][j]=total; c[i][j]=tcost; } } } } if(cs!=1)cout<<endl; cout<<"Case #"<<cs++<<endl; fi(1, q){ cin>>u>>v; if(dis[u][v]>=inf) cout<<-1<<endl; else cout<<dis[u][v]+c[u][v]<<endl; } } return 0; }

Floyd Warshsall - Implementation (C++)

/* Bismillahir Rahmanir Rahim Implementation of "Floyd Warshall" (C++) All pair shortest path */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) #define ll long long using namespace std; ll dis[300][300]; int main(){ ll n, e, u, v, w; cin>>n>>e; for(ll i=1; i<=n; i++){ for(ll j=1; j<=n; j++){ if(i==j)dis[i][j]=0; else dis[i][j]=1000000009; } } fi(0, e-1){ cin>>u>>v>>w; dis[u][v]=w; } for(ll k=1; k<=n; k++){ for(ll i=1; i<=n; i++){ for(ll j=1; j<=n; j++){ dis[i][j]=min(dis[i][j], (dis[i][k]+dis[k][j])); } } } for(ll i=1; i<=n; i++){ for(ll j=1; j<=n; j++) cout<<dis[i][j]<<" "; cout<<endl; } return 0; }