I badly need it. My code gives correct output for every input given here in electronic board. But i m still getting wrong answer.
![:evil:](./images/smilies/icon_evil.gif)
Moderator: Board moderators
Code: Select all
1
AA BB
AA CC
Code: Select all
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
# define MAX 1500
using namespace std;
int s[MAX];
vector<string> v(MAX);
vector<int> d(MAX);
vector<string>dest(MAX);
int cost[MAX][MAX];
vector <int> p(MAX);
int compi(string str,int *count)
{
for(int i=0;i<(*count);i++)
{
if(str==v[i])
return i;
}
(*count)++;
return ((*count)-1);
}
int main()
{
char a[5],b[5];
int n;
int i;
string so,des;
while(cin>>n)
{ int count=0;
if(n==0)
{
cin>>a;
cin>>b;
cout<<"No route \n\n";
continue;
}
for(i=0;i<n;i++)
{
cin>>a;
cin>>b;
int j=compi(a,&count);
v[j]=a;
int k=compi(b,&count);
v[k]=b;
cost[j][k]=1;
cost[k][j]=1;
}
cin>>so;
int source=compi(so,&count);
cin>>des;
int desti=compi(des,&count);
int z1=-1,z2=-1;
for(i=0;i<=count;i++)
for(int j=0;j<=count;j++)
{ if(i==j)
cost[i][j]=0;
else if(cost[i][j]!=1)
cost[i][j]=9999;
}
for(i=0;i<count;i++)
{
if(cost[source][i]!=0 && cost[source][i]!=9999)
{
z1=1;
}
if(cost[desti][i]!=0 && cost[desti][i]!=9999)
{
z2=1;
}
if(z1==1 && z2==1)break;
}
if(z1==-1 || z2==-1){ cout<<"No route\n\n";continue;}
for(i=0;i<count;i++)
{
p[i]=source;
s[i]=0;
d[i]=cost[source][i];
}
s[source]=1;
int r=1;
int flag=0;
for(int i=1;i<count;i++)
{
int min1=9999;
int u=-1;
for(int j=0;j<count;j++)
{
if(s[j]==0)
{
if(d[j]<min1)
{
min1=d[j];
u=j;
}
}
}
if(u==(-1)){flag=1 ; break;}
s[u]=1;
if(u==desti)break;
for(int v=0;v<count;v++)
{
if(s[v]==0)
{
if(d[u]+cost[u][v]<d[v])
{ d[v]=d[u]+cost[u][v];p[v]=u;}
}
}
}
if(flag==0)
{
int i=desti;
r=0;
while(i!=source)
{
dest[r++]=v[i];
i=p[i];
}
dest[r++]=v[source];
for(int i=r-1;i>=1;i--)
{
cout<<dest[i]<<" "<<dest[i-1]<<"\n";
}cout<<"\n";
}
else
cout<<"No route\n\n";
}
return 0;
}
Code: Select all
#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
#define oo 100000000
struct edge{
int source,dest,cost; // source and destination and cost for the edge
edge(){}
edge(int s,int d,int c):source(s),dest(d),cost(c){}
};
struct node{
int parent,dist; // the parent and the distance between the node and its parent
node(){}
node(int p,int d):parent(p),dist(d){}
};
/*
* Bellman Ford ShortestPath algorithm works with negative costs but it works on edges not on points
* edges vector must be created before calling the method
* n is the number of nodes
*/
vector<node> BellmanFordSP(vector<edge> & edges,int source,int n){
vector<node> nodes;
// initializing
int i,j;
for(i=0;i<n;i++)
nodes.push_back(node(-1,oo));
nodes[source].dist = 0;
//
for(i=0;i<n;i++){
bool flag = true;
for(j=0;j<edges.size();j++){
//Relaxation
if(nodes[edges[j].dest].dist > nodes[edges[j].source].dist + edges[j].cost){
flag = false;
nodes[edges[j].dest].dist = nodes[edges[j].source].dist + edges[j].cost;
nodes[edges[j].dest].parent = edges[j].source;
}
}
if(flag) break; // No more relaxation can be done
}
for(i=0;i<edges.size();i++){ // To detect negative cycles
if(nodes[edges[i].dest].dist > nodes[edges[i].source].dist + edges[i].cost){
nodes.clear(); // Negative Cycle detected return empty vector
break;
}
}
return nodes;
}
map<string,int> m;
map<int,string> m2;
void printPath(vector<node> v,int s,int d)
{
if(v.size()==0){ cout<<"No route\n"; return;}
vector<string> p;
while(d!=s)
{
if(d == -1) {
cout<<"No route\n"; return;
}
p.push_back(m2[d]);
d = v[d].parent;
}
p.push_back(m2[s]);
for(int i=p.size()-1;i>0;i--)
{
cout<<p[i]<< " "<< p[i-1]<<endl;
}
}
int main()
{
freopen("test.in","r",stdin);
vector<edge> edges;
int n;
string str1,str2;
int t=0;
while(cin>>n)
{
if(t) cout<<"\n";
t++;
for(int i=0;i<n;i++)
{
cin>>str1>>str2;
if(m.find(str1) == m.end())
{
m[str1] = m.size();
m2[m[str1]] = str1;
}
if(m.find(str2) == m.end())
{
m[str2] = m.size();
m2[m[str2]] = str2;
}
edges.push_back(edge(m[str1],m[str2],1));
edges.push_back(edge(m[str2],m[str1],1));
}
cin>>str1>>str2;
if(m.find(str1)==m.end() || m.find(str2) == m.end())
cout<<"No route\n";
else
printPath(BellmanFordSP(edges,m[str1],m.size()) , m[str1],m[str2]);
edges.clear();
m.clear();
m2.clear();
}
return 0;
}
Code: Select all
input:
1
AA BB
AA DD
1
AA BB
AA AA
output:
No route
AA AA
Code: Select all
Removed after AC
Code: Select all
1
AA AA
MM MM
Code: Select all
MM MM
What can i say? I have got about 15 WAYou may assume that the input is valid and consistent.