Submission #1286091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286091		Jawad_Akbar_JJ	Robot (JOI21_ho_t4)	C++20	24 / 100	309 ms	39656 KiB

Main

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

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

void Add(int u, int v, int d){
	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 dijkstra(int u){
	for (int i=2;i<N;i++)
		Min[i] = 1e17;
	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});
			}
		}
	}
}

signed 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);

	dijkstra(1);

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

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