Submission #1185158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185158		witek_cpp	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	1095 ms	7412 KiB

ho_t4

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
 
using namespace std;
typedef long long ll;
 
#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()

const ll DUZO = 1'000'000'000'000'000'000;

ll wnk = DUZO;
 
int n, m;
map<pair<pair<int, int>, pair<ll, ll>>, int> wstp;
vector<pair<pair<int, int>, pair<ll, ll>>> krawedzie;
vector<vector<ll>> odl;
vector<vector<int>> ile; //ile minimalnych krawedzi wychodzi z i do j
vector<vector<pair<ll, ll>>> macierz_sasiedztwa;

vector<ll> wyniki_dijkstra;

ll dijkstra(int zrodlo) {
	f(i, 1, n + 1) {
		wyniki_dijkstra[i] = -1;
	}
	
	priority_queue<pair<ll, int>> kolejka;
	
	kolejka.push({0, zrodlo});
	
	pair<ll, int> p1;
	
	while (!kolejka.empty()) {
		p1 = kolejka.top();
		kolejka.pop();
		if (wyniki_dijkstra[p1.nd] != -1) continue;
		wyniki_dijkstra[p1.nd] = -p1.st;
		f(i, 1, n + 1) {
			if (wyniki_dijkstra[i] != -1 || i == p1.nd || macierz_sasiedztwa[p1.nd][i].st == -1) continue;
			kolejka.push({p1.st - macierz_sasiedztwa[p1.nd][i].st, i});
		}
	}
	if (zrodlo == 1) return wyniki_dijkstra[n];
	return wyniki_dijkstra[1];
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    int w1, w2;
    ll w3, w4;
    odl.resize(n + 1, vector<ll>(n + 1, DUZO));
    
    f(i, 1, (n + 1)) odl[i][i] = 0;
    
    f(i, 0, m) {
        cin >> w1 >> w2 >> w3 >> w4;
        if (wstp.find({{w1, w2}, {w3, w4}}) != wstp.end()) continue;
        wstp[{{w1, w2}, {w3, w4}}] = 1;
        krawedzie.pb({{w1, w2}, {w3, w4}});
        odl[w1][w2] = min(odl[w1][w2], w3);  
    }
    
    f(k, 1, (n + 1)) f(u, 1, (n + 1)) f(v, 1, (n + 1)) odl[u][v] = min(odl[u][v], odl[u][k] + odl[k][v]);
    
    ile.resize(n + 1, vector<int>(n + 1, 0));
   
    macierz_sasiedztwa.resize(n + 1, vector<pair<ll, ll>>(n, {DUZO, DUZO}));
    
    for (pair<pair<int, int>, pair<ll, ll>> ele: krawedzie) {
		if (macierz_sasiedztwa[ele.st.st][ele.st.nd].st > ele.nd.st) {
			macierz_sasiedztwa[ele.st.st][ele.st.nd].nd = macierz_sasiedztwa[ele.st.st][ele.st.nd].st;
			macierz_sasiedztwa[ele.st.st][ele.st.nd].st = ele.nd.st;
		}
		macierz_sasiedztwa[ele.st.st][ele.st.nd].nd = min(macierz_sasiedztwa[ele.st.st][ele.st.nd].nd, ele.nd.st);
	} 
	
	f(i, 1, n + 1) {
		f(j, 1, n + 1) {
			f(k, 1, n + 1) {
				if (macierz_sasiedztwa[i][k].st <= 1'000'000 && ((macierz_sasiedztwa[i][k].st + odl[k][j]) == odl[i][j])) ile[i][j]++;
				if (macierz_sasiedztwa[i][k].nd <= 1'000'000 && ((macierz_sasiedztwa[i][k].nd + odl[k][j]) == odl[i][j])) ile[i][j]++;
			}
		}
	}
	
	pair<ll, ll> p1;
	pair<ll, ll> p2;
	
	wyniki_dijkstra.resize(n + 1);
	
	//cout << "git\n";
	
	for (pair<pair<int, int>, pair<ll, ll>> ele: krawedzie) {
		if (((odl[1][ele.st.st] + ele.nd.st + odl[ele.st.nd][n]) > odl[1][n]) && (ile[ele.st.st][n] > 1)) {
			wnk = min(wnk, odl[1][n] + odl[n][ele.st.nd] + odl[ele.st.st][1] + ele.nd.st + ele.nd.nd);
		} else {
			if (macierz_sasiedztwa[ele.st.nd][ele.st.st].st > ele.nd.st) {
				//cout << "a ";
				p1 = macierz_sasiedztwa[ele.st.nd][ele.st.st];
				p2 = macierz_sasiedztwa[ele.st.st][ele.st.nd];
				macierz_sasiedztwa[ele.st.nd][ele.st.st].st = ele.nd.st;
				if (macierz_sasiedztwa[ele.st.st][ele.st.nd].st == ele.nd.st) {
					macierz_sasiedztwa[ele.st.st][ele.st.nd].st = macierz_sasiedztwa[ele.st.st][ele.st.nd].nd;
				}
				//cout << "krawedz " << ele.st.st << " " << ele.st.nd << "   " << ele.nd.st << "\n";
				wnk = min(wnk, dijkstra(1) + dijkstra(n) + ele.nd.nd);
				macierz_sasiedztwa[ele.st.nd][ele.st.st] = p1;
				macierz_sasiedztwa[ele.st.st][ele.st.nd] = p2;
			}
		}
	}
	if (wnk >= (2'000'000'000)) {
		cout << -1 << "\n";
	} else {
		cout << wnk << "\n";
	}
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63