Submission #1248442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248442		Noname_1900	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	450 ms	53552 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100000;
#define int long long
const int INFINI = 1e17;
struct T {
    int noeud, temps, anc;
    bool operator<(const T &other)  const {
        return temps > other.temps;
    }
};
int nbVilles, nbChemins, maison, ecole, point1, point2;
vector<T> chemins[NMAX];
int dejaVu[NMAX];
vector<int> ancNoeud[NMAX];
int miniTemps[NMAX];
vector<int> grapheGratuit[2][NMAX];
void construire(int noeud)
{
    if(noeud == -1) return;
    if(dejaVu[noeud] == 2)  return;
    dejaVu[noeud] = 2;
    for(auto pro : ancNoeud[noeud])
    {
       // cout << noeud << " " << pro << endl;
        if(pro == -1)   continue;
        grapheGratuit[1][noeud].push_back(pro);
        grapheGratuit[0][pro].push_back(noeud);
        construire(pro);
    }
}
struct C {
    int noeud, temps, autorisations;
    bool operator<(const C &other)  const {
        return temps > other.temps;
    }
};
int dejaVuFin[4][NMAX];
signed main() {
	// your code goes here
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> nbVilles >> nbChemins >> maison >> ecole >> point1 >> point2;
    --maison;
    --ecole;
    --point1;
    --point2;
    
    for(int iChemin = 0; iChemin < nbChemins; iChemin++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        --a;
        --b;
        chemins[a].push_back({b, t, -1});
        chemins[b].push_back({a, t, -1});
    }
	for(int i = 0; i < nbVilles; i++)
	{
		miniTemps[i] = INFINI;
	}
    priority_queue<T> plusCourtChemin;
    plusCourtChemin.push({maison, 0, -1});
    while(plusCourtChemin.size())
    {
        auto sit = plusCourtChemin.top();
        plusCourtChemin.pop();
        if(dejaVu[sit.noeud] == 1)
        {
            if(miniTemps[sit.noeud] == sit.temps)
            {
                ancNoeud[sit.noeud].push_back(sit.anc);
            }
            continue;
        }
       // cout << sit.noeud+1 << " " << sit.temps << endl;
        ancNoeud[sit.noeud].push_back(sit.anc);
        dejaVu[sit.noeud] = 1;
        miniTemps[sit.noeud] = sit.temps;
        for(auto pro : chemins[sit.noeud])
        {
            plusCourtChemin.push({pro.noeud, pro.temps+sit.temps, sit.noeud});
        }
    }
    
    construire(ecole);
    /*
    for(int i = 0; i < nbVilles; i++)
    {
        cout << i+1 << " : ";
        for(int pro : grapheGratuit[0][i]) cout << pro+1 << " ";
        cout << endl;
        for(int pro : grapheGratuit[1][i])  cout << pro+1 << " ";
        cout << endl;
    }
        /** */
    priority_queue<C> plusCourtCheminFin;
    plusCourtCheminFin.push({point1, 0, 2});
    while(plusCourtCheminFin.size())
    {
        auto sit = plusCourtCheminFin.top();
        plusCourtCheminFin.pop();
        if(sit.noeud == point2)
        {
            cout << sit.temps;
            return 0;
        }
        
        if(dejaVuFin[sit.autorisations][sit.noeud] == true)    continue;
        dejaVuFin[sit.autorisations][sit.noeud] = true;
        if(dejaVuFin[2][sit.noeud] == true)
        {
            dejaVuFin[0][sit.noeud] = 1;
            dejaVuFin[1][sit.noeud] = 1;
        }
        if((dejaVuFin[0][sit.noeud] == 1) && (dejaVuFin[1][sit.noeud] == 1))    dejaVuFin[2][sit.noeud] = 1;
       // cout << sit.noeud+1 <a< " " << sit.temps << " " << sit.autorisations << endl;
        for(auto pro : chemins[sit.noeud])
        {
          if(sit.autorisations >= 2)
            plusCourtCheminFin.push({pro.noeud, pro.temps+sit.temps, sit.autorisations});
          else
            plusCourtCheminFin.push({pro.noeud, pro.temps+sit.temps, 3});
        }
        if(sit.autorisations == 2)
        {
            for(int i = 0; i < 2; i++)
            {
                for(auto pro : grapheGratuit[i][sit.noeud]) plusCourtCheminFin.push({pro, sit.temps, i});
            }
        }
        else if(sit.autorisations != 3)
        {
            for(auto pro : grapheGratuit[sit.autorisations][sit.noeud]) plusCourtCheminFin.push({pro, sit.temps, sit.autorisations});
        }
    }
    cout << -1;
}

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