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

Solution of Light OJ 1059 - Air Ports

/* Bismillahir Rahmanir Rahim Solution using (MST)Kruskal's 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; int pr[10001], n, m; set<int>st; struct edge{ int u, v, w; }one[100001]; bool comp(edge f, edge s){ return f.w<s.w; } int find(int p){ if(pr[p]==p) return p; else return find(pr[p]); } int mst(){ int sm=0, xx, yy, cnt=0; fi(1, n) pr[i]=i; fi(0, m-1){ xx=find(one[i].u); yy=find(one[i].v); if(xx!=yy){ pr[yy]=xx; cnt++; sm+=one[i].w; } if(cnt==n-1) return sm; } return sm; } int main(){ int t, c, cs=1, sz, ans, u, v, w, an; cin>>t; while(t--){ an=0; cin>>n>>m>>c; fi(0, m-1){ cin>>u>>v>>w; if(w<c){ one[i].u=u; one[i].v=v; one[i].w=w; } else{ // special case one[i].u=u; one[i].v=u; one[i].w=0; } } sort(one, one+m, comp); ans=mst(); fi(1, n){ st.insert(find(pr[i])); } sz=st.size(); cout<<"Case "<<cs++<<": "<<ans+(sz*c)<<" "<<sz<<endl; st.clear(); } return 0; }