এটা একটি শর্টেস্ট পাথ প্রবলেম। সর্বোচ্চ X টি নোড ব্যবহার করে ১ থেকে N তম নোডে যাবার শর্টেস্ট পাথ বের করতে হবে। সমস্যাটি কয়েকভাবে সমাধান করা যায়। একটি সমাধান হলো dijkstra ব্যবহার করা,এবং কারেন্ট নোডে কয়টি এজ ব্যবহার করে এসেছি তার হিসাব রাখা। সর্বোচ্চ Xটি নোড ব্যবহার করা যাবে এ কথাটিকে অন্যভাবে বলা যায় সর্বোচ্চ X+1 টি এজ ব্যবহার করা যাবে।
আরেকটা সমাধান হলো bellman ford। বেলম্যান ফোর্ডের মূল অ্যালগোরিদম এরকম:
|
1 2 3 4 5 6 7 8 9 10 |
//taken from topcoder for i = 1 to n d[i] = infinity d[source] = 0 for i = 1 to n-1 for all edges (u,v) in E if d[v] > d[u] + cost[u][v] d[v] = d[u] + cost[u][v]</code> |
বাইরে লুপটি ১বার শেষ হবার পর আমরা পাবো ১টি এজ ব্যবহার করে শর্টেস্ট পাথ,M বার শেষ হবার পর পাবো সর্বোচ্চ Mটি এজ ব্যবহার করে শর্টেস্ট পাথ। তবে এখানে এজ কোন অর্ডারে নিব সেটি গুরুত্বপূর্ণ। কাছের নোডগুলো আগে আপডেট করলে প্রথম ইটারেশনেই ২য় নোড দিয়ে পরেরগুলো আপডেট হয়ে যেতে পারে। তাই আপডেট করার সময় উল্টা করে করে করতে হবে,সোর্স থেকে দূরের এজগুলোকে আগে নিতে হবে।
আমার কোডটি এরকম:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
//Spoiler Warning: don't copy the code #include <cstdio> #include <iostream> #include <cstring> #include <map> #include <vector> using namespace std; #define INF 999999999 int main() { freopen("in","r",stdin); //freopen("out","w",stdout); int T,kas=0; cin>>T; while(T--) { int w[202][202]; int mat[102][102]; map<string,int>MP; memset(w,0,sizeof(w)); memset(mat,0,sizeof(mat)); vector<int>list; int N,i,E; cin>>N; for(i=1;i<=N;i++) { string S; cin>>S; MP[S]=i; } cin>>E; for(i=1;i<=E;i++) { string A,B; int x,y,cost; cin>>A>>B>>cost; x=MP[A]; y=MP[B]; if(w[x][y]) w[x][y]=min(w[x][y],cost); else w[x][y]=cost; mat[x][y]=1; } int Q; cin>>Q; printf("Scenario #%d\n",++kas); while(Q--) { int lim; cin>>lim; int d[202],j; for(i=1;i<=N;i++)d[i]=INF; d[1]=0; for(int loop=1;loop<=lim+1;loop++) { for(i=N;i>=1;i--) for(j=N;j>=1;j--) { if(mat[i][j]) d[j]=min(d[j],d[i]+w[i][j]); } } if(d[N]>=INF) puts("No satisfactory flights"); else printf("Total cost of flight(s) is $%d\n",d[N]); } if(T) puts(""); } return 0; } |
বেলম্যান ফোর্ড নিয়ে একটা চমতকার টিউটোরিয়াল: http://apps.topcoder.com/forums/?module=Thread&threadID=671406&start=0
ফেসবুকে মন্তব্য
Powered by Facebook Comments
ধন্যবাদ ভাই। আপনার এটা থেকে কিছু শিখে নিজে নিজে চেষ্টা করি।