Submission #697364

#	Time	Username	Problem	Language	Result	Execution time	Memory
697364		micjan	Robot (JOI21_ho_t4)	C++14	0 / 100	131 ms	28716 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define st first
#define nd second
#define FOR(i,j,k) for(auto i = (j); i<(k); i++)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define pb push_back
#define BOOST ios_base::sync_with_stdio(0);cin.tie(0);

const int MN = 1e5+10;
const int MM = 2e5+10;
const ll inf = 1e18+2;

vll S[MN];
ll d[MN];
bool odw[MN];

void Dijkstra(int s, int n)
{
	FOR(i,0,n+1) d[i] = inf;
	d[s] = 0;
	priority_queue<pll> Q;
	Q.push({-d[s],s});
	while(!Q.empty())
	{
		int v = Q.top().nd;
		Q.pop();
		if(odw[v]) continue;
		odw[v] = 1;
		for(auto& e:S[v])
		{
			if(d[e.st]>d[v]+e.nd)
			{
				d[e.st] = d[v]+e.nd;
				Q.push({-d[e.st],e.st});
			}
		}
	}
}

ll Koszt[MM];//koszt jaki trzeba zapłacić żeby przejść danym kolorem
ll C[MM];//kolor i tej krawędzi
vii S2[MN];//sąsiad, numer kr
ll P[MM];//koszt zmiany i tej krawędzi

int main()
{
	BOOST;
	int n,m;
	cin>>n>>m;
	FOR(i,0,m)
	{
		int a,b;
		cin>>a>>b>>C[i]>>P[i];
		S2[a].pb({b,i});
		S2[b].pb({a,i});
	}
	FOR(v,0,n)
	{
		for(auto& e:S2[v])
			Koszt[C[e.nd]]+=P[e.nd];

		for(auto& e:S2[v])
		{
			ll k = min(P[e.nd], Koszt[C[e.nd]]-P[e.nd]);
			S[v].pb({e.st, k});
		}

		for(auto& e:S2[v])
			Koszt[C[e.nd]]-=P[e.nd];
	}
	Dijkstra(1,n);
	if(d[n]==inf) cout<<-1;
	else cout<<d[n];
}

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