Submission #1286089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286089		Jawad_Akbar_JJ	Robot (JOI21_ho_t4)	C++20	24 / 100	242 ms	28036 KiB

Main

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1<<17;
vector<pair<int,pair<int,int>>> Vec[N], Raw[N];
vector<pair<int,int>> nei[N];
int seen[N], Min[N];

void Add(int u, int v, int d, int flg = 0){
	// cout<<u<<" ";
	// cout<<(flg ? '-' : '<');
	// cout<<"---> "<<v<<" "<<" "<<d<<'\n';
	
	nei[u].push_back({v, d});
}

void dfs(int u){
	seen[u] = 1;
	sort(begin(Raw[u]), end(Raw[u]));

	for (int i=0;i<Raw[u].size();i++){
		auto [a1, b1] = Raw[u][i];

		int j = i, Sm = b1.second;
		while (j + 1 < Raw[u].size() and Raw[u][j+1].first == a1)
			j++, Sm += Raw[u][j].second.second;

		for (int k=i;k<=j;k++){
			auto [a, b] = Raw[u][k];
			Add(u, b.first, min(b.second, Sm - b.second));
			if (seen[b.first] == 0)
				dfs(b.first);
		}
		if (j == i + 1){
			auto [a2, b2] = Raw[u][i+1];
			Add(b1.first, b2.first, b1.second);
			Add(b2.first, b1.first, b2.second);
		}
		i = j;
	}
}

void dfs2(int u){
	seen[u] = 2;
	sort(begin(Vec[u]), end(Vec[u]));

	for (int i=0, id = 0;i<Raw[u].size();i++){
		auto [a1, b1] = Raw[u][i];

		int j = i, Sm = b1.first;
		while (j + 1 < Raw[u].size() and Raw[u][j+1].first == a1)
			j++, Sm += Raw[u][j].second.second;

		
		for (int k=i;k<=j;k++){
			auto [a, b] = Raw[u][k];
			if (seen[b.first] != 2)
				dfs2(b.first);
			while (id < Vec[u].size() and Vec[u][id].first == a and Vec[u][id].second.first == b.first)
				Add(u, Vec[u][id].second.second, min(b.second, Sm - b.second), 1), id++;
		}
		i = j;
	}
}

void dijkstra(int u){
	for (int i=2;i<N;i++)
		Min[i] = 1e9;
	set<pair<int,int>> st = {{0, 1}};

	while (st.size() > 0){
		auto [mn, u] = *begin(st);
		st.erase(begin(st));

		for (auto [i, w] : nei[u]){
			if (Min[u] + w < Min[i]){
				st.erase({Min[i], i});
				Min[i] = Min[u] + w;
				st.insert({Min[i], i});
			}
		}
	}
}

int main(){
	int n, m;
	cin>>n>>m;

	for (int i=1, a, b, c, d;i<=m;i++){
		cin>>a>>b>>c>>d;
		Raw[a].push_back({c, {b, d}});
		Raw[b].push_back({c, {a, d}});
	}


	dfs(1);

	// dfs2(1);

	// return 0;

	dijkstra(1);

	if (Min[n] == 1e9)
		Min[n] = -1;
	cout<<Min[n]<<'\n';
}

• Subtask 1: 0 / 34
• Subtask 2: 24 / 24
• Subtask 3: 0 / 42