Submission #1235869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235869		inesfi	Museum (CEOI17_museum)	C++20	0 / 100	3092 ms	320 KiB

museum

#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define endl "\n"

struct route {
    int deb,fin,vitesse,longueur;
};

struct pos {
    double temps;
    int num_ville,vitesse_avant;
    int ville_avant,vitesse_encore_avant;

    bool operator<(const pos& autre) const {
        return temps<autre.temps;
    }
};

const int VILLEMAXI=152,VITESSEMAXI=502;
vector<int> adja[VILLEMAXI];
vector<route> routes;
set<pos> encours;
double dist[VILLEMAXI][VITESSEMAXI];
pair<int,int> avant[VILLEMAXI][VITESSEMAXI]; // ville,vitesse

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int nbvilles,nbroutes,destination;
    cin>>nbvilles>>nbroutes>>destination;
    for (int i=0;i<nbroutes;i++){
        route r;
        cin>>r.deb>>r.fin>>r.vitesse>>r.longueur;
        routes.push_back(r);
        adja[r.deb].push_back(i);
    }
    for (int i=0;i<nbvilles;i++){
        for (int j=0;j<VITESSEMAXI;j++){
            dist[i][j]=-1;
        }
    }
    encours.insert({0,0,70,-1,-1});
    //int compt=0;
    bool ok=false;
    int vitessefin=0;
    while (ok==false){
        //compt++;
        pos ec=*encours.begin();
        encours.erase(encours.begin());
        if (ec.num_ville==destination){
            dist[ec.num_ville][ec.vitesse_avant]=ec.temps;
            vitessefin=ec.vitesse_avant;
            avant[ec.num_ville][ec.vitesse_avant]={ec.ville_avant,ec.vitesse_encore_avant};
            ok=true;
        }
        else {
            if (dist[ec.num_ville][ec.vitesse_avant]==-1){
                dist[ec.num_ville][ec.vitesse_avant]=ec.temps;
                avant[ec.num_ville][ec.vitesse_avant]={ec.ville_avant,ec.vitesse_encore_avant};
                for (auto v:adja[ec.num_ville]){
                    int nouv_vitesse=ec.vitesse_avant;
                    if (routes[v].vitesse!=0){
                        nouv_vitesse=routes[v].vitesse;
                    }
                    pos nouv;
                    nouv.temps=ec.temps+(double)routes[v].longueur/(double)nouv_vitesse;
                    nouv.num_ville=routes[v].fin;
                    nouv.vitesse_avant=nouv_vitesse;
                    nouv.ville_avant=ec.num_ville;
                    nouv.vitesse_encore_avant=ec.vitesse_avant;
                    if (dist[nouv.num_ville][nouv.vitesse_avant]==-1){
                        encours.insert(nouv);
                    }
                }
            }
        }
    }
    //cout<<42<<endl;
    //return 0;
    vector<int> rep={};
    int ville_ec=destination,vitesse_ec=vitessefin;
    while (ville_ec!=0){
        rep.push_back(ville_ec);
        int nvil=avant[ville_ec][vitesse_ec].first;
        int nvit=avant[ville_ec][vitesse_ec].second;
        ville_ec=nvil;
        vitesse_ec=nvit;
    }
    rep.push_back(0);
    reverse(rep.begin(),rep.end());
    for (auto r:rep){
        cout<<r<<" ";
    }
    cout<<endl;
    //cout<<dist[destination][vitessefin]<<endl;
    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20