Problem Link: https://onlinejudge.org/external/11/1112.pdf
Note:
Though the problem gives the vibe of a 2D Dijkstra as it is about the cells, after reading about the input format and after seeing the sample input, it can be understood that it is a straightforward 1D application of Dijkstra.
And about the input format, we do not have to bother with the blank lines because “std::cin” by nature isn’t bothered with those blank lines. You can follow this link for more added knowledge on this.
Code:
#include <bits/stdc++.h>
#define MAX 100005
#define INF INT_MAX
#define pii pair<int,int>
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
using namespace std;
int dijkstra(int src, int dst, vector<vector<pii>> &adj)
{
vector<int> dis(MAX, INF);
//dis[100005]={INT_MAX} ; why doesn't work(gives wrong answer) I don't know!
dis[src]=0;
priority_queue<pii, vector<pii>, greater<pii> >pq;
pq.push({0, src}); // Insert source in priority queue and initialize its distance as 0.
while(!pq.empty())
{
int u=pq.top().second;
int cost=pq.top().first;
pq.pop();
//Optimization in the priority queue:
/*
Ideally, for updating the priority queue, we must delete the old value and reinsert with the
new cost value. But, as we know that the updated cost value is always lesser than the old
value and would be popped from the queue and visited before the old value,
we could save time and avoid removing the old value from the queue.
*/
if(dis[u]<cost) continue;
for(int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first;
cost=adj[u][i].second;
if(dis[v]>dis[u]+cost)
{
dis[v]=dis[u]+cost;
pq.push({dis[v], v});
}
}
}
return dis[dst];
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
cin>>t;
while(t--)
{
int node, dst, end_time;
cin>>node>>dst>>end_time;
int edge;
cin>>edge;
vector<vector<pair<int,int> > > adj(node+1);
for(int i=0; i<edge; i++)
{
int from,to,time;
cin>>from>>to>>time;
adj[from].push_back({to, time});
}
int ans=0;
for(int i=1; i<=node; i++)
{
int src=i;
int min_distace=dijkstra(src, dst, adj);
if(min_distace<=end_time) ans++;
}
cout<<ans<<endl;
if(t>0) cout<<endl;
}
return 0;
}
Fall out, Codes! 