Submission #1090598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090598		Octa_pe_info	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	312 ms	25544 KiB

commuter_pass

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct arbore {

    int nod,cost;

    bool operator>(arbore other)const {

        return cost > other.cost;

    }

};

struct arbore2 {

    int nod,cost,stare;

};

int n,m,u,v,s,t;
int rez=1e9;
vector<vector<arbore>>tabel;
vector<vector<int>>drumuri;
vector<int>d;

void dij(int start,int sf) {

    priority_queue<arbore,vector<arbore>,greater<arbore>>pq;

    pq.push({start,0});

    while(!pq.empty()) {

        arbore curent = pq.top();
        pq.pop();

        if(d[curent.nod] < curent.cost)
            continue;

        for(auto i : tabel[curent.nod]) {

            if(d[i.nod] > curent.cost + i.cost) {

                d[i.nod] = curent.cost + i.cost;
                pq.push({i.nod,d[i.nod]});

            }

        }

    }

}

void rec(int start,int sf) {

    queue<arbore2>q;

    int mx=0;

    drumuri[0].push_back(start);

    q.push({start,d[start],0});

    while(!q.empty()) {

        arbore2 curent = q.front();
        q.pop();

        if(curent.nod == sf)
            continue;

        int cnt= 0;

        for(auto i : tabel[curent.nod]) {

            if(d[i.nod] == curent.cost - i.cost) {

                if(cnt == 0) {

                    drumuri[curent.stare].push_back(i.nod);
                    q.push({i.nod,d[i.nod],curent.stare});
                    cnt++;
                    mx = max(mx,curent.stare);

                } else {

                    int nou = mx + 1;

                    drumuri[nou] = drumuri[curent.stare];
                    drumuri[nou].push_back(i.nod);
                    cnt++;
                    q.push({i.nod,d[i.nod],nou});
                    mx = max(mx,nou);

                }
            }

        }

    }

}

void calc(vector<vector<arbore>>&tabel2) {

    priority_queue<arbore,vector<arbore>,greater<arbore>>pq;
    vector<int>di(n+1,1e9);
    pq.push({u,0});

    di[u]=0;

    while(!pq.empty()) {

        arbore curent = pq.top();
        pq.pop();

        if(di[curent.nod] < curent.cost)
            continue;

        for(auto i : tabel2[curent.nod]) {

            if(di[i.nod] > curent.cost + i.cost) {

                di[i.nod] = curent.cost + i.cost;
                pq.push({i.nod,di[i.nod]});

            }

        }

    }

    rez = min(rez,di[v]);

}


int main() {

    cin>>n>>m>>s>>t>>u>>v;

    tabel.resize(n+1);
    d.resize(n+1,1e9);
    drumuri.resize(n+1);

    for(int i=1; i<=m; i++) {

        int a,b,c;
        cin>>a>>b>>c;

        tabel[a].push_back({b,c});
        tabel[b].push_back({a,c});

    }

    /// dist de la s la t

    dij(s,t);

    /// reconstruiesc

    rec(t,s);

    ///verific

    for(auto i : drumuri){

        cout<<endl;

        for(auto j : i)
            cout<<j<<" ";

    }

    for(int i=0;i<drumuri.size();i++){

        if(drumuri[i].size() == 0)
            break;

        vector<vector<arbore>>nou = tabel;

        for(int j=0;j<drumuri[i].size()-1;j++){

            nou[drumuri[i][j]].push_back({drumuri[i][j+1],0});
            nou[drumuri[i][j+1]].push_back({drumuri[i][j],0});

        }

        calc(nou);

    }

    cout<<rez;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |     for(int i=0;i<drumuri.size();i++){
      |                 ~^~~~~~~~~~~~~~~
commuter_pass.cpp:187:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |         for(int j=0;j<drumuri[i].size()-1;j++){
      |                     ~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45