ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1072. Routing

WA#8 . Give some tests, please
Posted by Lex [PNTU] 31 Mar 2011 01:23
I use dijkstra algo, what's wrong?
code



#include <cstdio>
#include <vector>
#include <map>
#include <set>
using namespace std;
const long long INF=100000000;
typedef unsigned long long ULL;
typedef pair<long long,long long> pii;
typedef vector<vector<long long> > VVI;
typedef vector<long long> vi;
typedef map<long long,vi> MIV;
MIV network;
VVI G;

long long n=1,n_int;
void init_vert(){
        for (long long i=0;i<=n;++i){
                vector< long long > temp;
                G.push_back(temp);
            }
        for (MIV::iterator it=network.begin();it!=network.end();++it){
            for(vi::iterator vit=it->second.begin();vit!=it->second.end();++vit){
                for(vi::iterator vit2=it->second.begin();vit2!=it->second.end();++vit2){
                    G[*vit].push_back(*vit2);
                }
            }
        }
    }

long long read_network(){
    long long res=0;
    long long mask=0;
    long r1,r2,r3,r4;
    long m1,m2,m3,m4;
    scanf("%ld.%ld.%ld.%ld",&r1,&r2,&r3,&r4);
    scanf("%ld.%ld.%ld.%ld",&m1,&m2,&m3,&m4);

    res+=r1&m1;res<<8;
    res+=r2&m2;res<<8;
    res+=r3&m3;res<<8;
    res+=r4&m4;

        return res;
    }


vector<long long> dist,parent;


void dejkstra(long long s){
    dist.assign(n+1,INF);
    parent.assign(n+1,INF);
    dist[s]=0;
    set<pair<long long,long long>  > q;
    q.insert(make_pair(dist[s],s));
    while (!q.empty()){
            long long v=q.begin()->second;
            q.erase(q.begin());
            for (size_t j=0;j<G[v].size();++j){
                    long long to=G[v][j];
                    if (dist[v]+1<dist[to]){
                            q.erase(make_pair(dist[to],to));
                            dist[to]=dist[v]+1;
                            parent[to]=v;
                            q.insert(make_pair(dist[to],to));
                        }
                }
        }
    }

int main(){
        //freopen("in","r",stdin);
        scanf("%lld",&n);
        long long n_n_m=0;
        for (size_t i=0;i<n;++i){
            scanf("%lld",&n_int);
            for (size_t j=0;j<n_int;++j){
                n_n_m=read_network();
                network[n_n_m].push_back(i+1);
            }
        }
        init_vert();
        long long _beg,_end;
        scanf("%lld%lld",&_beg,&_end);
        dejkstra(_beg);


        if (dist[_end]==INF){
                printf("No\n");
                return 0;
            }
        else{
                printf("Yes\n");
                long long p=_end;
                vector<long long>res;
                printf("%lld ",_beg);

                while(p!=_beg){
//                        printf(">>>%d\n",p);
                        res.push_back(p);
                        p=parent[p];


                    }
                 for (vi::reverse_iterator it=res.rbegin();it!=res.rend();++it){
                        printf("%lld ",*it);
                    }

                printf("\n");
            }
        return 0;
    }
My Bellman–Ford solution. WA#8 too. ((
Posted by Lex [PNTU] 31 Mar 2011 14:14
#include <cstdio>
#include <vector>
#include <map>
#include <set>
using namespace std;
const long long INF=10000;

typedef unsigned long long ULL;
typedef unsigned long UL;
typedef pair<int,int> pii;
typedef vector<int> vi;
int n=0,n_int=0;

vector<pair<int,int> > G;
map<UL,vi > network;


void init_vert(){
        for (map<UL,vi >::iterator it=network.begin();it!=network.end();++it){
            for(vi::iterator vit=it->second.begin();vit!=it->second.end();++vit){
                for(vi::iterator vit2=it->second.begin();vit2!=it->second.end();++vit2){
                    if ( ( *vit ) != ( *vit2 ) ){
                            G.push_back(make_pair(*vit,*vit2));
                        }
                }
            }

        }
    }

UL read_network(){
    UL res=0;
    long r1,r2,r3,r4;
    long m1,m2,m3,m4;
    scanf("%ld.%ld.%ld.%ld",&r1,&r2,&r3,&r4);
    scanf("%ld.%ld.%ld.%ld",&m1,&m2,&m3,&m4);

    res+=r1&m1;res<<4;
    res+=r2&m2;res<<4;
    res+=r3&m3;res<<4;
    res+=r4&m4;
    return res;
    }


vector<long> dist;
vector<int> parent;

void FB(int start,int end){
        dist.assign(n,INF);
        parent.assign(n,-1);
        dist[start]=0;
        for (size_t i=0;i<n;++i){
                for (vector<pair<int,int> >::iterator it=G.begin();it!=G.end();++it){
                        if (dist[it->first]<INF){
                                if(dist[it->second]>dist[it->first]+1){

                                        dist[it->second]=dist[it->first]+1;
                                        parent[it->second]=it->first;
                                    }
                            }
                    }
            }
    }



int main(){
        freopen("in","r",stdin);
        scanf("%d",&n);
        UL n_n_m=0;

        for (size_t i=0;i<n;++i){
            scanf("%d",&n_int);
            for (size_t j=0;j<n_int;++j){
                n_n_m=read_network();
                network[n_n_m].push_back(i);
            }
        }
        init_vert();
        int _beg,_end;

        scanf("%d%d",&_beg,&_end);

        FB(_beg-1,_end-1);

        if (parent[_end-1]==-1){
                printf("No\n");
                return 0;
            }
        else{
                printf("Yes\n");
                int p=_end-1;
                vector<int> res;
                while(p!=_beg-1){
                        res.push_back(p);
                        p=parent[p];
                    }
                printf("%d ",_beg);
                for (vi::reverse_iterator it=res.rbegin();it!=res.rend();++it){
                        printf("%d ",(*it)+1);
                    }

                printf("\n");
            }
        return 0;
    }
I'm so stupid
Posted by Lex [PNTU] 3 Apr 2011 13:09
res<<4 => res<<=4 + AC)
Re: I'm so stupid
Posted by [TH0412]Le Phuc Tai 28 Nov 2012 09:39
 hi Lex why res<<=4
Re: I'm so stupid
Posted by [TH2011/01]1112384 28 Nov 2012 19:53
[TH0412]Le Phuc Tai wrote 28 November 2012 09:39
hi Lex why res<<=4
a<<=8 <==> a = a<<8

Edited by author 28.11.2012 19:53