Here is my code I’ve tried all test cases available on spojtoolkit all of them gave correct answer. but still I get WA when i submit. Can anyone help me with this
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
// A structure to represent an adjacency list node
struct AdjListNode
{
int dest;
int wt;
struct AdjListNode* next;
};
// A structure to represent an adjacency list
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};
// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};
// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest,int weight)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->wt = weight;
newNode->next = NULL;
return newNode;
}
// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest,int weight)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the begining
struct AdjListNode* newNode = newAdjListNode(dest,weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
int minDistance(int n,long long int risk[n+1],bool set[n+1]){
int min_index;
long long int min = INT_MAX ;
for(int i=1;i<n+1;i++){
if(risk[i]<=min&&set[i]==false)
min = risk[i],min_index = i;
}
return min_index;
}
void path(struct Graph* rgraph, struct Graph* tgraph,long long int ans,int src,int des){
int n = rgraph->V - 1,i,u;
long long int risk[n+1],time[n+1];
bool set[n+1];
for(i=1;i<n+1;i++)
risk[i] = INT_MAX,set[i] = false,time[i]=0;
risk[src]=0;
for(i=1;i<=n&&set[des]==false;i++){
u = minDistance(n,risk,set);
//printf("%d %lld\n",u,risk[des] );
set[u]=true;
struct AdjListNode pCrawl = rgraph->array[u].head;
struct AdjListNode* tCrawl = tgraph->array[u].head;
if(u==des){
ans[0]= risk[des];
ans[1] = time[des];
return;
}
else{
while(pCrawl){
if(risk[u]!=INT_MAX&&risk[u]+pCrawl->wt<risk[pCrawl->dest]){
risk[pCrawl->dest] = risk[u]+pCrawl->wt;
time[pCrawl->dest] = time[u]+tCrawl->wt;
}
pCrawl= pCrawl->next;
tCrawl=tCrawl->next;
}
}
}
ans[0]= risk[des];
ans[1] = time[des];
return;
}
void printGraph(struct Graph* graph)
{
int v;
for (v = 1; v < graph->V; ++v)
{
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head “, v);
while (pCrawl)
{
printf(”-> %d %d", pCrawl->dest,pCrawl->wt);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
int main()
{
int t,n;
scanf("%d",&n);
scanf("%d",&t);
while(n||t){
int a,i,j,risk,time;
long long int ans,min_risk=INT_MAX,min_time=INT_MAX;
ans = (long long int )malloc(2sizeof(long long int));
struct Graph tgraph = createGraph(n+1);
struct Graph* rgraph = createGraph(n+1);
for(i=1;i<n+1;i++){
for(j=1;j<=n;j++){
scanf("%d",&a);
addEdge(tgraph,i,j,a);
}
}
for(i=1;i<n+1;i++){
for(j=1;j<=n;j++){
scanf("%d",&a);
addEdge(rgraph,i,j,a);
}
}
//printGraph(rgraph);
path(rgraph,tgraph,ans,1,n);
if(ans[1]<=t){
if(ans[0]<=0){
ans[0]=ans[0](t/ans[1]);
ans[1]=ans[1](t/ans[1]);
}
printf("%lld %lld\n",ans[0],ans[1] );
}
else{
for(i=1;i<n-1;i++){
path(rgraph,tgraph,ans,1,n-i);
risk = ans[0];
time = ans[1];
path(rgraph,tgraph,ans,n-i,n);
risk+=ans[0];
time+=ans[1];
if(risk<min_risk&&time<=t)
min_risk = risk,min_time =time;
}
if(min_time<=t)
printf("%lld %lld\n",min_risk,min_time );
else
printf("-1\n");
}
scanf("%d",&n);
scanf("%d",&t);
}
}