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; }