Submission #699179

#	Time	Username	Problem	Language	Result	Execution time	Memory
699179		Markomafko972	Robot (JOI21_ho_t4)	C++14	0 / 100	76 ms	14172 KiB

Main

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, m, a, b, c, d;
vector< pair<int, pii> > v[100005];
ll dist[100005];
set< pair<ll, int> > s;
set<int> boja[100005];
int kol[200005];

void dijkstra() {
	
	
	while (!s.empty()) {
		ll cost = s.begin() -> first;
		int cvor = s.begin() -> second;
		s.erase(s.begin());
		
		for (int i = 0; i < v[cvor].size(); i++) kol[v[cvor][i].Y.X]++;
		while (!boja[cvor].empty()) {
			kol[*(boja[cvor].begin())]--;
			boja[cvor].erase(boja[cvor].begin());
		}
		
		for (int i = 0; i < v[cvor].size(); i++) {
			int sus = v[cvor][i].X;
			int cijena = v[cvor][i].Y.Y;
			if (kol[v[cvor][i].Y.X] == 1) cijena = 0;
			
			if (cost+cijena < dist[sus]) {
				s.erase({dist[sus], sus});
				dist[sus] = cost+cijena;
				s.insert({dist[sus], sus});
			
				boja[sus].clear();
				boja[sus].insert(v[cvor][i].Y.X);
			}
			else if (cost+cijena == dist[sus]) {
				boja[sus].insert(v[cvor][i].Y.X);
			}
		}
		
		for (int i = 0; i < v[cvor].size(); i++) kol[v[cvor][i].Y.X] = 0;
	}
	
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c >> d;
		v[a].push_back({b, {c, d}});
		v[b].push_back({a, {c, d}});
	}
	
	s.insert({0, 1});
	for (int i = 2; i <= n; i++) {
		dist[i] = INF;
		s.insert({INF, i});
	}
	
	dijkstra();
	
	if (dist[n] == INF) cout << -1;
	else cout << dist[n];

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dijkstra()':
Main.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for (int i = 0; i < v[cvor].size(); i++) kol[v[cvor][i].Y.X]++;
      |                   ~~^~~~~~~~~~~~~~~~
Main.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for (int i = 0; i < v[cvor].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~
Main.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int i = 0; i < v[cvor].size(); i++) kol[v[cvor][i].Y.X] = 0;
      |                   ~~^~~~~~~~~~~~~~~~

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