Getiing WA in this problem. Here's the code:
Code: Select all
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
#define NIL 0
#define MAX 500
#define INF 99999999
typedef struct Node_
{
int id,d;
} Node_;
bool visited[MAX+1];
bool visitedByBoss[MAX+1];
vector<Node_> adj[MAX+1];
int d[MAX+1],pre[MAX+1];
int v,E,home,office,shop,bossHome;
int findMin();
void markPath(int,int);
void main()
{
int i,u,j;
int m,n,cost;
Node_ next,temp;
while(scanf("%d %d %d %d %d %d",&v,&E,&bossHome,&office,&home,&shop) == 6)
{
for( i = 1; i <= v; i++)
{
adj[i].clear();
d[i] = INF;
}
d[bossHome] = 0;
for( i = 0; i < E; i++)
{
scanf("%d %d %d",&m,&n,&cost);
temp.id = n;temp.d = cost;
adj[m].push_back(temp);temp.id = m;
adj[n].push_back(temp);
}
memset(visited,false,sizeof(visited));
memset(visitedByBoss,false,sizeof(visitedByBoss));
memset(pre,NIL,sizeof(pre));
visitedByBoss[bossHome] = true;
for( i = 0 ; i < v - 1; i++)
{
u = findMin();
visited[u] = true;
for( j = 0; j < adj[u].size(); j++)
{
next = adj[u][j];
if(!visited[next.id])
{
if(d[next.id] > d[u] + next.d)
{
d[next.id] = d[u] + next.d;
pre[next.id] = u;
}
}
}
}
markPath(bossHome,office);
if(visitedByBoss[home] || visitedByBoss[shop])
{
puts("MISSION IMPOSSIBLE.");
continue;
}
memset(visited,false,sizeof(visited));
for( i = 1; i <= v; i++) d[i] = INF;
d[home] = 0;
for( i = 0; i < v - 1; i++)
{
u = findMin();
visited[u] = true;
if( !visitedByBoss[u] )
{
for( j = 0; j < adj[u].size(); j++)
{
next = adj[u][j];
if( !visited[next.id])
{
if(d[next.id] > d[u] + next.d)
d[next.id] = d[u] + next.d;
}
}
}
}
if(d[shop] >= INF) puts("MISSION IMPOSSIBLE.");
else printf("%d\n",d[shop]);
}
}
int findMin()
{
int i,minIndex,Min = INF;
for( i = 1; i <= v; i++)
{
if( !visited[i])
{
if( d[i] < Min)
{
Min = d[i];
minIndex = i;
}
}
}
return minIndex;
}
void markPath(int s,int t)
{
if( pre[t] == NIL ) return;
else
{
visitedByBoss[t] = true;
markPath(s,pre[t]);
}
}
This code handles the terminal cases(all the req. points are same or some of them are same). But getting WA. Can some1 chk this plz. Or give me some suggestions | | sample I/O.
