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

Solution of Light OJ 1174-Commandos

/* بسم الله الرحمن الرحيم Solution - using "Dijkstra". Calculate the shortest path for all node from both starting node and ending node then mx=max(mx, (d1[i]+d2[i])) */ #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; vector<int>vt[101], cost[101]; int d1[101], d2[101], n; struct node{ int u, w; node(int a, int b){ u=a, w=b; } bool operator < (const node & p)const{ return p.w<w; } }; void dijkstra(int st){ priority_queue<node>q; fi(0, n-1)d1[i]=100009; d1[st]=0; q.push(node(st, 0)); while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; int sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; if(d1[u]+cost[u][i]<d1[v]){ d1[v]=d1[u]+cost[u][i]; q.push(node(v, d1[v])); } } } } void ddijkstra(int st){ priority_queue<node>q; fi(0, n-1) d2[i]=100009; d2[st]=0; q.push(node(st, 0)); while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; int sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; if(d2[u]+cost[u][i]<d2[v]){ d2[v]=d2[u]+cost[u][i]; q.push(node(v, d2[v])); } } } } int main(){ int t, u, v, e, st, cs=1, en, a1, a2, mx; cin>>t; while(t--){ mx=0; cin>>n>>e; fi(0, e-1){ cin>>u>>v; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(1); cost[v].push_back(1); } cin>>st>>en; /* input end */ dijkstra(st); ddijkstra(en); fi(0, n-1) mx=max(mx, (d1[i]+d2[i])); cout<<"Case "<<cs++<<": "<<mx<<endl; fi(0, n-1){ vt[i].clear(); cost[i].clear(); } } return 0; }

Solution of Light OJ 1019 - Brush (V)

/* Bismillahir Rahmanir Rahim Solution-Using Dijkstra algorithm */ #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; vector<int>vt[109], cost[109]; int dis[109], n; struct node{ int u, w; node(int a, int b){ u=a, w=b; } bool operator < (const node & p)const{ return p.w<w; } }; void dijkstra(int st){ priority_queue<node>q; fi(0, n)dis[i]=1000001; dis[st]=0; q.push(node(st, 0)); while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; int sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; if(dis[u]+cost[u][i]<dis[v]){ dis[v]=dis[u]+cost[u][i]; q.push(node(v, dis[v])); } } } } int main(){ int t, cs=1, e, u, v, w; cin>>t; while(t--){ cin>>n>>e; fi(0, e-1){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } dijkstra(1); cout<<"Case "<<cs++<<": "; if(dis[n]==1000001)cout<<"Impossible"<<endl; else cout<<dis[n]<<endl; fi(0, n){ vt[i].clear(); cost[i].clear(); } } return 0; }

Solution of Light OJ 1002 - Country Roads

/* Bismillahir Rahmanir Rahim Solution using Dijkstra algorithm. */ #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; vector<int>vt[1009], cost[1009]; int dis[1009], n; struct node{ int u, w; node(int a, int b){ u=a, w=b; } bool operator < (const node & p)const{ return p.w<w; } }; void dijkstra(int st){ priority_queue<node>q; fi(0, n)dis[i]=20001; dis[st]=0; q.push(node(st, 0)); while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; int sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; int temp=max(dis[u], cost[u][i]); if(temp<dis[v]){ dis[v]=temp; q.push(node(v, dis[v])); } } } } int main(){ int e, u, v, w, m, t, cs=1; cin>>t; while(t--){ cin>>n>>e; fi(0, e-1){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } cin>>m; dijkstra(m); cout<<"Case "<<cs++<<":"<<endl; fi(0, n-1){ if(dis[i]==20001)cout<<"Impossible"<<endl; else cout<<dis[i]<<endl; } fi(0, n-1){ vt[i].clear(); cost[i].clear(); } } return 0; }

Dijkstra Algorithm - Implementation with C++

/* Bismillahir Rahmanir Rahim Dijkstra algorithm implementation(C++) Shortest path for all nodes from given node */ #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; vector<int>vt[1009], cost[1009]; int dis[1009]; struct node{ int u, w; node(int a, int b){ u=a, w=b; } bool operator < (const node & p)const{ return p.w<w; } }; void dijkstra(int st){ priority_queue<node>q; memset(dis, 63, sizeof(dis)); dis[st]=0; q.push(node(st, 0)); while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; int sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; if(dis[u]+cost[u][i]<dis[v]){ dis[v]=dis[u]+cost[u][i]; q.push(node(v, dis[v])); } } } } int main(){ int n, e, u, v, w, m; cin>>n>>e; while(e--){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } cin>>m; // from this node dijkstra(m); fi(1, n)cout<<m<<" to "<<i<<" = "<<dis[i]<<endl; return 0; }