I got the RTE.Please help me.I had test the city AA to ZZ. There are 26*26 cities.
#include<iostream>
#include<fstream>
#include<string>
#include<queue>
#include<stack>
using namespace std;
string city_num[700];
int num_total_city;
bool m[700][700],inside,findend=0;
queue<int> q;
stack<string> p;
int father[700],from_num,to_num;
int searching(string s){
int i;
for(i=0;i<num_total_city;i++){
if(city_num==s){
return i;
}
}
return -1;
}
void bfs(int i){
int j;
if(i<0) return;
for(j=0;j<num_total_city;j++){
if(m[j]){
if(father[j]==-1) father[j]=i;
if(j==to_num){
findend=true;
return;
}
q.push(j);
m[j]=false;
}
}
while(!q.empty()){
i=q.front();
for(j=0;j<num_total_city;j++){
if(m[j]){
if(father[j]==-1) father[j]=i;
if(j==to_num){
findend=true;
return;
}
q.push(j);
m[j]=false;
}
}
q.pop();
}
}
int main()
{
ifstream fin;
fin.open("7.txt");
istream& input(cin);
ofstream fout;
fout.open("5.txt");
int i,j,num1,num2,n;
string city[1400],from,to;
char x;
while(input>>n){
for(i=0;i<700;i++){
for(j=0;j<700;j++){
m[j]=false;
}
}
while(!p.empty()) p.pop();
while(!q.empty()) q.pop();
findend=false;
for(i=0;i<700;i++){
city_num="";
father=-1;
}
for(i=0;i<1400;i++){
city="";
}
for(i=0;i<n*2;i++){
input>>city;
}
input>>from>>to;
num_total_city=0;
for(i=0;i<n*2;i++){
inside=false;
for(j=0;j<num_total_city;j++){
if(city[i]==city_num[j]){
inside=true;
}
}
if(!inside){
city_num[num_total_city]=city[i];
num_total_city++;
}
}
for(i=0;i<n*2;i=i+2){
num1=searching(city[i]);
num2=searching(city[i+1]);
m[num1][num2]=true;
m[num2][num1]=true;
}
/*for(i=0;i<num_total_city;i++){
for(j=0;j<num_total_city;j++){
fout<<m[i][j];
}
fout<<endl;
}*/
from_num=searching(from);
to_num=searching(to);
bfs(from_num);
p.push(to);
i=to_num;
while(father[i]!=-1){
i=father[i];
p.push(city_num[i]);
}
//p.push(from);
if(!findend&&to!=from){
cout<<"No route"<<endl;
}
if(findend){
while(!p.empty()){
cout<<p.top()<<" ";
p.pop();
cout<<p.top()<<endl;
if(p.size()==1) break;
}
}
cout<<endl;
}
return 0;
}
762 - We Ship Cheap
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 762 - We Ship Cheap
Don't open files.
Check input and AC output for thousands of problems on uDebug!
Re: 762 - We Ship Cheap
Can anybody help me?
I'm getting WA and I've passed every test case discussed in this thread.
thanks in advance
I'm getting WA and I've passed every test case discussed in this thread.
Code: Select all
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
map<int, vi> graph;
map<string, string> parent;
map <string, int> indexes;
map <int, string> cities;
void backtrack(string begin, string end) {
stack<string> path;
string x = end;
while (true) {
if (parent.count(x)) {
path.push(x);
x = parent[x];
}
else break;
}
string last;
for (int i = 0; i < (int)path.size(); i++) {
cout << parent[path.top()] << " " << path.top() << endl;
last = path.top();
path.pop();
}
if (last != end)
cout << last << " " << end << endl;
}
int main () {
int t, cont = 0;
while (scanf("%d", &t) != EOF) {
if (cont)
printf("\n");
int idx = 0;
graph.clear();
indexes.clear();
parent.clear();
cities.clear();
for (int i = 0; i < t; i++) {
string a, b;
cin >> a >> b;
if (!indexes.count(a)) {
indexes[a] = idx;
cities[idx] = a;
idx++;
}
if (!indexes.count(b)) {
indexes[b] = idx;
cities[idx] = b;
idx++;
}
graph[indexes[a]].push_back(indexes[b]);
graph[indexes[b]].push_back(indexes[a]);
}
string init, dest;
cin >> init >> dest;
if (init == dest) {
cout << init << " " << dest << endl;
cont++;
continue;
}
if (!indexes.count(init)) {
printf("No route\n");
cont++;
continue;
}
int begin = indexes[init];
int end = indexes[dest];
queue<int> q;
q.push(begin);
map<int, int> dist;
dist[begin] = 0;
bool found = false;
while (!q.empty() && !found) {
int u = q.front();
q.pop();
for (int i = 0; i < (int)graph[u].size(); i++) {
int v = graph[u][i];
if (!dist.count(v)) {
dist[v] = dist[u] + 1;
q.push(v);
parent[cities[v]] = cities[u];
if (v == end) {
found = true;
break;
}
}
}
}
if (found) {
backtrack(init, dest);
}
else
printf("No route\n");
cont ++;
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 762 - We Ship Cheap
Input:AC output No route
Code: Select all
1
AA BB
BB CC
Check input and AC output for thousands of problems on uDebug!
Re: 762 - We Ship Cheap
Why getting RE!!!please help
I've tested all the inputs discusssed in this forum
I've tested all the inputs discusssed in this forum
Code: Select all
#include<bits/stdc++.h>
using namespace std;
map<string,int>m;
vector<int>v[100];
int visited[100];
int parent[100];
vector<int>sv;
vector<string>ss;
void bfs(int src,int d)
{
queue<int>q;
memset(visited,-1,sizeof(visited));
memset(parent,-1,sizeof(parent));
visited[src]=0;
q.push(src);
int u,r;
while(!q.empty())
{
int a=q.front();
q.pop();
for(int i=0;i<v[a].size();i++)
{
u=v[a][i];
if(visited[u]==-1)
{
visited[u]=visited[a]+1;
parent[u]=a;
q.push(u);
}
if(u==d)break;
}
}
if(visited[d]==-1){cout<<"No route"<<endl;return;}
r=d;
sv.push_back(r);
r=parent[r];
while(r!=src)
{
sv.push_back(r);
r=parent[r];
}
sv.push_back(r);
reverse(sv.begin(),sv.end());
for(int i=0;i<sv.size()-1;i++)
cout<<ss[sv[i]]<<" "<<ss[sv[i+1]]<<endl;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
string s,s1;
char x,y,z;
int l=0,i,edge;
bool p=0;
while(scanf("%d",&edge)!=EOF)
{
//if(edge==0){cin>>s>>s1;continue;}
l=0;
if(p)cout<<endl;
for(int k=0;k<edge;k++)
{
cin>>s>>s1;
if(m.find(s)==m.end()){m[s]=l;ss.push_back(s);l++;}
if(m.find(s1)==m.end()){m[s1]=l;ss.push_back(s1);l++;}
v[m[s]].push_back(m[s1]);
v[m[s1]].push_back(m[s]);
}
cin>>s>>s1;
if(s==s1)cout<<s<<" "<<s1<<endl;
else if(m.find(s)==m.end()||m.find(s1)==m.end())cout<<"No route"<<endl;
else bfs(m[s],m[s1]);
ss.clear();
m.clear();
for(int k=0;k<100;k++)v[k].clear();
sv.clear();
p=true;
getchar();
}
//else return 0;
return 0;
}
-
- New poster
- Posts: 1
- Joined: Wed Mar 01, 2017 6:36 pm
Re: 762 - We Ship Cheap
Why I am getting WA
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000
map<string,ll>mp;
map<ll,string>mp2;
bool vis[100005];
ll dis[100005];
vector<ll>vec[100005];
ll par[100005];
void bfs(ll uu)
{
queue<ll>Q;
Q.push(uu);
dis[uu] = 0;
while(!Q.empty())
{
ll u = Q.front();
Q.pop();
for(ll i = 0; i<vec.size(); i++)
{
ll v = vec;
if(dis[v] == inf)
{
dis[v] = dis + 1;
par[v] = u;
Q.push(v);
}
}
}
}
int main()
{
// freopen("in.txt","rt",stdin);
//freopen("out.txt","wt",stdout);
ll node,cn = 0;
while(scanf("%lld",&node) == 1)
{
if(cn>0) cout<<endl;
cn++;
ll i = 0,nod = node;
string a,b;
ll kk = node;
while(nod--)
{
cin>>a>>b;
if(mp[a] == 0)
{
i++;
mp[a] = i;
mp2 = a;
}
if(mp == 0)
{
i++;
mp = i;
mp2 = b;
}
vec[mp[a]].push_back(mp);
vec[mp].push_back(mp[a]);
}
cin>>a>>b;
if(a == b)
{cout<<a<<" "<<a<<endl;
continue;
}
else if(mp[a] == 0 || mp == 0)
{
cout<<"No route"<<endl;
continue;
}
par[mp[a]] = -1;
for(ll i=0; i<=100003; i++)dis=inf;
bfs(mp[a]);
if(dis[mp] == inf) cout<<"No route"<<endl;
else
{
vector<ll>path;
ll x = mp;
path.push_back(x);
while(par[x]!=-1)
{
path.push_back(par[x]);
x = par[x];
}
reverse(path.begin(),path.end());
cout<<mp2[path[0]]<<" "<<mp2[path[1]]<<endl;
if(path.size()>2)
{
for(ll k = 2; k<path.size(); k++)
cout<<mp2[path[k-1]]<<" "<<mp2[path[k]]<<endl;
}
}
for(ll k = 0; k<=100003; k++)
vec[k].clear();
mp.clear();
mp2.clear();
}
return 0;
}
/*
3
JV PT
KA PT
KA HP
JV HP
2
JV PT
KA HP
JV HP
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000
map<string,ll>mp;
map<ll,string>mp2;
bool vis[100005];
ll dis[100005];
vector<ll>vec[100005];
ll par[100005];
void bfs(ll uu)
{
queue<ll>Q;
Q.push(uu);
dis[uu] = 0;
while(!Q.empty())
{
ll u = Q.front();
Q.pop();
for(ll i = 0; i<vec.size(); i++)
{
ll v = vec;
if(dis[v] == inf)
{
dis[v] = dis + 1;
par[v] = u;
Q.push(v);
}
}
}
}
int main()
{
// freopen("in.txt","rt",stdin);
//freopen("out.txt","wt",stdout);
ll node,cn = 0;
while(scanf("%lld",&node) == 1)
{
if(cn>0) cout<<endl;
cn++;
ll i = 0,nod = node;
string a,b;
ll kk = node;
while(nod--)
{
cin>>a>>b;
if(mp[a] == 0)
{
i++;
mp[a] = i;
mp2 = a;
}
if(mp == 0)
{
i++;
mp = i;
mp2 = b;
}
vec[mp[a]].push_back(mp);
vec[mp].push_back(mp[a]);
}
cin>>a>>b;
if(a == b)
{cout<<a<<" "<<a<<endl;
continue;
}
else if(mp[a] == 0 || mp == 0)
{
cout<<"No route"<<endl;
continue;
}
par[mp[a]] = -1;
for(ll i=0; i<=100003; i++)dis=inf;
bfs(mp[a]);
if(dis[mp] == inf) cout<<"No route"<<endl;
else
{
vector<ll>path;
ll x = mp;
path.push_back(x);
while(par[x]!=-1)
{
path.push_back(par[x]);
x = par[x];
}
reverse(path.begin(),path.end());
cout<<mp2[path[0]]<<" "<<mp2[path[1]]<<endl;
if(path.size()>2)
{
for(ll k = 2; k<path.size(); k++)
cout<<mp2[path[k-1]]<<" "<<mp2[path[k]]<<endl;
}
}
for(ll k = 0; k<=100003; k++)
vec[k].clear();
mp.clear();
mp2.clear();
}
return 0;
}
/*
3
JV PT
KA PT
KA HP
JV HP
2
JV PT
KA HP
JV HP
*/
Re: 762 - We Ship Cheap
Your code gets compile error.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman