Submission #1109053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109053		Ivo_12	Robot (JOI21_ho_t4)	C++17	100 / 100	2445 ms	148440 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair < ll, ll >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

const ll N = 1e5+10, M = 2e5+10;

ll n, m;
map < pii, vector < pair < ll, ll > > > adjc;
vector < pair < pii, ll > > adj[N];
map < pii, bool > vis;
ll price[N];

using namespace std;

void task( void ) {
	
	ll a, b, c;
	ll p;
	cin >> n >> m;
	for(ll i = 0; i < m; i++) {
		cin >> a >> b >> c >> p;
		a--; b--; c--;
		adj[a].pb(mp(mp(b, c), p));
		adj[b].pb(mp(mp(a, c), p));
		adjc[mp(a, c)].pb(mp(b, p));
		adjc[mp(b, c)].pb(mp(a, p));
	}
	
	ll tempsum;
	vector < pair < ll, ll > > :: iterator itrs, itre;
	for(ll i = 0; i < n; i++) {
		for(ll j = 0; j < (ll) adj[i].size(); j++) {
			if(!vis[mp(i, adj[i][j].F.S)]) {
				tempsum = 0;
				vis[mp(i, adj[i][j].F.S)] = 1;
				
				itrs = adjc[mp(i, adj[i][j].F.S)].begin();
				itre = adjc[mp(i, adj[i][j].F.S)].end();
				while(itrs != itre) {
					tempsum += itrs -> S;
					itrs++;
				}
				
				itrs = adjc[mp(i, adj[i][j].F.S)].begin();
				while(itrs != itre) {
					adj[i].pb(mp(mp(itrs -> F, -1), tempsum - (itrs -> S)));
					itrs++;
				}
			}
		}
		
		for(ll j = 0; j < (ll) adj[i].size(); j++) {
			vis[mp(i, adj[i][j].F.S)] = 0;
		}
	}
	
	set < pair < ll, pii > > dijkstra;
	dijkstra.insert(mp(0, mp(0, -1)));
	
	pair < ll, pii > temp;
	ll pos, col, val;
	
	while(!dijkstra.empty()) {
		temp = *dijkstra.begin();
		dijkstra.erase(dijkstra.begin());
		pos = temp.S.F;
		col = temp.S.S;
		val = temp.F;
//		cout << pos << "  " << col << "  " << val << "\n";
		
		if(!vis[mp(pos, -1)]) {
			vis[mp(pos, -1)] = 1;
			price[pos] = val;
			for(ll i = 0; i < (ll) adj[pos].size(); i++) {
		
				if((!vis[mp(adj[pos][i].F.F, adj[pos][i].F.S)]) && adj[pos][i].F.S != -1) {
					vis[mp(adj[pos][i].F.F, adj[pos][i].F.S)] = 1;
					tempsum = 0;
					itrs = adjc[mp(adj[pos][i].F.F, adj[pos][i].F.S)].begin();
					itre = adjc[mp(adj[pos][i].F.F, adj[pos][i].F.S)].end();
					while(itrs != itre) {
						tempsum += itrs -> S;
						itrs++;
					}
					itrs = adjc[mp(adj[pos][i].F.F, adj[pos][i].F.S)].begin();
					while(itrs != itre) {
						dijkstra.insert(mp(val + tempsum - (itrs -> S), mp(itrs -> F, -1)));
						itrs++;
					}
				}
			
				dijkstra.insert(mp(val + adj[pos][i].S, mp(adj[pos][i].F.F, adj[pos][i].F.S)));
			}
		}
	}
	
	if(vis[mp(n - 1, -1)]) cout << price[n - 1] << "\n";
	else cout << -1 << "\n";	
	
	return;
}

int main( void ) {
	
	FIO;
	task();
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void task()':
Main.cpp:68:10: warning: variable 'col' set but not used [-Wunused-but-set-variable]
   68 |  ll pos, col, val;
      |          ^~~

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