oj.uz

Submission #697364

# Submission time Handle Problem Language Result Execution time Memory
697364 2023-02-09T12:52:21 Z micjan Robot (JOI21_ho_t4) C++14
0 / 100
 131 ms 28716 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Incorrect 4 ms 5176 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 14164 KB Output is correct
2 Correct 22 ms 9152 KB Output is correct
3 Correct 73 ms 19940 KB Output is correct
4 Correct 35 ms 11292 KB Output is correct
5 Incorrect 131 ms 28716 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Incorrect 4 ms 5176 KB Output isn't correct
10 Halted 0 ms 0 KB -