Submission #413001

#	Time	Username	Problem	Language	Result	Execution time	Memory
413001		Chaska	Robot (JOI21_ho_t4)	C++11	0 / 100	629 ms	56536 KiB

Main

#include <bits/stdc++.h> 
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())
#define PI 3.141592
#define fo(i,n) for (int i=0;i<n;i++)
#define fofo(i,n,j,m) for (int i=0;i<n;i++) for (int j=0;j<m;j++) 
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int N=1e5+5,M=2e5+5,mod=1e9+7;

ll n,m;
map<ll,ll> h[N];
map<ll,ll> hp[N];
vector<ll> g[N];
map<ii,ll> pr;
map<ii,ll> co;
bool vs[N];
map<ll,vector<ll>> back[N];
ll res[N];
priority_queue<ii,vector<ii>,greater<ii>> pq;
void dij(ll cost,ll node)
{
	if (vs[node]) return;
	vs[node] = true;
	res[node] = cost;
	//cout << node << " "<< res[node] << "\n";
	for (int u : g[node]) {
		int colorcito = co[{node,u}];
		if (!vs[u]) if ( h[node][colorcito]==1) {
			pq.push({cost,u});
			//dij(u,cost);
			///cout << node << " " << u << "\n"; 	
		}
	}
	for (int u : g[node]) {
		int colorcito = co[{node,u}];
		ll precioo = pr[{node,u}];
		if (!vs[u]) if (h[node][colorcito]>1) {
			pq.push({cost+min(precioo,hp[node][colorcito]-precioo),u});
		///	cout << node << " " << u << "\n";
			if (precioo <= hp[node][colorcito]-precioo) {
				//h[node][colorcito]--;
				h[u][colorcito]--;
				hp[u][colorcito] -= precioo;
				//hp[node][colorcito] -= precioo;
			} else {
				for (int v : back[node][colorcito]) {
					h[v][colorcito]--;
					hp[v][colorcito] -= pr[{node,v}];
				}
				h[u][colorcito]++;
				hp[u][colorcito] += pr[{node,u}];
				h[u][colorcito] = 1;
			
			}
			//dij(u,cost);
		}
	}
}

int main() { 
	cin.tie(0); cout.tie(0); 
	ios_base::sync_with_stdio();
	cin >> n >> m;
	for (int i=0;i<m;i++) {
		ll a,b,c,p;
		cin >> a >> b >> c >> p;
		co[{a,b}] = c;
		co[{b,a}] = c;
		pr[{a,b}] = p;
		pr[{b,a}] = p;
		g[a].push_back(b);
		g[b].push_back(a);
		back[a][c].push_back(b);
		back[b][c].push_back(a);
		h[a][c]++;
		hp[a][c] += p;
		h[b][c]++;
		hp[b][c] += p;
	}
	pq.push({0,1});
	while (!pq.empty()) {
		auto x = pq.top();
		pq.pop();
		dij(x.fi,x.se);
	}
	if (!vs[n]) cout << -1;
	else cout << res[n];
	return 0;
}

// Recuerda limites 
// Recuerda casos especiales

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