Submission #1188104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188104		Noname_1900	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	1481 ms	327680 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1000000;
#define int long long
const int INFINI = 1e15;
struct T {
    int noeud, temps;
    bool operator<(const T &other)  const {
        return temps > other.temps;
    }
};
int nbVilles, nbChemins, maison, ecole, point1, point2;
vector<T> chemins[NMAX];
int distancePoint[2][NMAX];
int dejaVu[NMAX];
vector<int> anc[NMAX];
struct C {
    int noeud, temps, dernier;
    bool operator<(const C &other)  const {
        return temps > other.temps;
    }
};
pair<int, int> dejaVuMinCout[NMAX];
bool vu[NMAX];
pair<int, int> trouverMinCout(int noeud)
{
	if(noeud == -1)	return pair<int, int>(INFINI, INFINI);
    if(vu[noeud])    return dejaVuMinCout[noeud];
    int meillPoint[2] = {distancePoint[0][noeud], distancePoint[1][noeud]};
	//cout << noeud << " : " << meillPoint[0] << " " << meillPoint[1] << endl;

    int meill = INFINI, meill1 = INFINI, meill2 = INFINI;
	for(int pro : anc[noeud])
	{
		auto rev = trouverMinCout(pro);
		int score = min(rev.first+rev.second, min(rev.first + meillPoint[1], rev.second+meillPoint[0]));
		if(meill > score)
		{
			meill = score;
			meill1 = rev.first;
			meill2 = rev.second;
		}
	}
    
    meillPoint[0] = min(meillPoint[0], meill1);
    meillPoint[1] = min(meillPoint[1], meill2);
    vu[noeud] = true;
	//cout << noeud << " : " << meillPoint[0] << " " << meillPoint[1] << endl;
    return dejaVuMinCout[noeud] = pair<int, int>(meillPoint[0], meillPoint[1]);
    
}
int miniTemps[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});
        chemins[b].push_back({a, t});
    }
	for(int i = 0; i < nbVilles; i++)
	{
		miniTemps[i] = INFINI;
	}
    for(int i = 0; i < 2; i++)
    {
        priority_queue<T> plusCourtChemin;
        plusCourtChemin.push({point1, 0});
        while(plusCourtChemin.size())
        {
            auto sit = plusCourtChemin.top();
            plusCourtChemin.pop();
            if(dejaVu[sit.noeud] == i+1)
                continue;
            dejaVu[sit.noeud] = i+1;
            distancePoint[i][sit.noeud] = sit.temps;
            for(auto pro : chemins[sit.noeud])
            {
                plusCourtChemin.push({pro.noeud, pro.temps+sit.temps});
            }
        }
        swap(point1, point2);
    }
	/*
	for(int i = 0; i < 2; i++)
	{
		for(int n = 0; n < nbVilles;n++)
		{
			cout << distancePoint[i][n] << " ";
		}
		cout << endl;
	}
		/** */
    priority_queue<C> plusCourtChemin2;
    plusCourtChemin2.push({maison, 0, -1});
    
    while(plusCourtChemin2.size())
    {
        auto sit = plusCourtChemin2.top();
        plusCourtChemin2.pop();
        miniTemps[sit.noeud] = min(miniTemps[sit.noeud], sit.temps);
		//cout << sit.noeud << " " << sit.dernier << " " << sit.temps << endl;

		if(sit.temps == miniTemps[sit.noeud])
		{
			//cout << "Bon" << endl;
			anc[sit.noeud].push_back(sit.dernier);
		}
		else
			continue;
        
        if(sit.noeud == ecole)
        {
			continue;
        }
            
        int a = 0;
        for(auto pro : chemins[sit.noeud])
        {
			a ++;
            plusCourtChemin2.push({pro.noeud, pro.temps+sit.temps, sit.noeud});
        }
		//cout << a << endl;
        
    }
	
	/**
	for(int i = 0; i < nbVilles; i++)
	{
		for(auto a : anc[i])	cout << a <<"  ";
			cout <<endl;
	}
	cout << endl;
	//return 0;
	/** */
    pair<int, int> res = trouverMinCout(ecole);
    cout << min(res.first + res.second, distancePoint[0][point2]);
}

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