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

Lex [PNTU] WA#8 . Give some tests, please [4] // Problem 1072. Routing 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;
    }
Lex [PNTU] My Bellman–Ford solution. WA#8 too. (( [3] // Problem 1072. Routing 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;
    }
Lex [PNTU] I'm so stupid [2] // Problem 1072. Routing 3 Apr 2011 13:09
res<<4 => res<<=4 + AC)
[TH0412]Le Phuc Tai Re: I'm so stupid [1] // Problem 1072. Routing 28 Nov 2012 09:39
 hi Lex why res<<=4
[TH2011/01]1112384 Re: I'm so stupid // Problem 1072. Routing 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