oj.uz

답안 #758938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758938 2023-06-15T14:54:37 Z jer033 Voting Cities (NOI22_votingcity) C++17
0 / 100
 23 ms 500 KB 
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

ll const big = 2000000000;
ll const ultrabig = 12000000000000;
ll const infinity = 1234567890123456;

ll edges[20007];
ll lastedgeindex[5007];

ll tempo[5007];
ll final[5007];

ll edgedecoder(ll edge, ll id)
{
	if (id==0)
		return edge/ultrabig;
	if (id==2)
		return edge%big;
	return (edge/big)%6000;
}

ll startindex(ll lastedgeindex[5007], ll i)
{
	if (i==0)
		return 0;
	return lastedgeindex[i-1]+1;
}

int main()
{
	ll n, e, k;
	cin >> n >> e >> k;
	ll edgecount=0;
	for (ll i=1; i<=k; i++)
	{
		ll votingbooth;
		cin >> votingbooth;
		votingbooth+=1;
		edges[edgecount] = votingbooth*big;
	}
	for (ll i=1; i<=e; i++)
	{
		ll ui, vi, ci;
		cin >> ui >> vi >> ci;
		ui+=1;
		vi+=1;
		edges[edgecount] = vi*ultrabig+ui*big+ci;
		edgecount++;
	}
	sort(edges, edges+edgecount);
	edges[edgecount]=-1;
	ll counter=0;
	for (ll city=0; city<=n; city++)
	{
		while (edgedecoder(edges[counter], 0)==city)
		{
			counter++;
		}
		lastedgeindex[city]=counter-1;
	}
	
	for (ll i=0; i<=n; i++)
	{
		tempo[i]=infinity;
		final[i]=infinity;
	}
	tempo[0]=0;
	final[0]=0;
	ll curr=0;
	for (ll iteration=1; iteration<=n; iteration++)
	{
		for (ll edgetocheck=startindex(lastedgeindex, curr); edgetocheck<=lastedgeindex[curr]; edgetocheck++)
		{
			ll newcity=edgedecoder(edges[edgetocheck], 1);
			ll travelcost=edgedecoder(edges[edgetocheck], 2);
			if (final[newcity]==infinity)
			{
				tempo[newcity]=min(tempo[newcity], final[curr]+travelcost);
			}
		}
		
		ll lowestcost=infinity;
		ll bestindex=n+1;
		for (ll city=1; city<=n; city++)
		{
			if (final[city]==infinity and tempo[city]<lowestcost)
			{
				lowestcost=tempo[city];
				bestindex=city;
			}
		}
		curr=bestindex;
		final[bestindex]=lowestcost;
	}
	
	ll q;
	cin >> q;
	for (ll query=1; query<=q; query++)
	{
		ll start, p1, p2, p3, p4, p5;
		cin >> start >> p1 >> p2 >> p3 >> p4 >> p5;
		start+=1;
		if (final[start]!=infinity)
			cout << final[start] << '\n';
		else
			cout << "-1\n";
	}
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -