Submission #714736

#	Time	Username	Problem	Language	Result	Execution time	Memory
714736		Iliya	Toll (BOI17_toll)	C++17	25 / 100	3069 ms	7692 KiB

toll

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
const int Inf = 0x3f3f3f3f;
vector<pair<int, int>> Adj[N], Order, Order2[N];
int n, m, k, o, C[N], D[N], mark[N], ans[N];
void Dijkstra(int v) 
{
	memset(D, 63, sizeof D);
	memset(mark, 0, sizeof mark);
	D[v] = 0;
	priority_queue<pair<int, int>> PQ;
	PQ.emplace(0, v);
	while (!PQ.empty()) 
	{
		int v = PQ.top().second; PQ.pop();
		if (mark[v]) continue;
		mark[v] = true;
		for (auto [u, w] : Adj[v]) 
			if (D[u] > D[v] + w)
				D[u] = D[v] + w, PQ.emplace(-D[u], u);
	}
}
void DFS(int v, int comp) 
{
	mark[v] = true;
	C[v] = comp;
	for (auto [u, w] : Adj[v])
		D[u] = D[v] + w, DFS(u, comp);
}
void Subtask1() 
{
	for (int i = 0; i < n; i++) 
		if (!mark[i]) DFS(i, i);
	for (auto [u, v] : Order) 
	{
		if (u < v) swap(u, v);
		if (C[u] == C[v]) 
			printf("%d\n", D[u] - D[v]);
		else 
			printf("%d\n", -1);
	}
}
signed main() 
{	
	scanf("%d%d%d%d", &k, &n, &m, &o);
	for (int i = 0; i < m; i++) 
	{
		int a, b, t;
		scanf("%d%d%d", &a, &b, &t);
		Adj[a].emplace_back(b, t);
	}
	vector<int> V;
	for (int i = 0; i < o; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		Order.emplace_back(a, b);
		Order2[a].emplace_back(b, i);
		V.push_back(a);
	}
	sort(V.begin(), V.end());
	V.resize(unique(V.begin(), V.end()) - V.begin());
	if (k == 1) {Subtask1(); return 0;}
	for (int x : V) 
	{
		Dijkstra(x);
		for (auto [u, i] : Order2[x])
			ans[i] = D[u];
	}
	for (int i = 0; i < o; i++) 
		printf("%d\n", (ans[i] == Inf ? -1 : ans[i]));
	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d%d%d", &k, &n, &m, &o);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d%d", &a, &b, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44