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