oj.uz

Submission #366715

# Submission time Handle Problem Language Result Execution time Memory
366715 2021-02-15T07:22:41 Z ChrisT Ceste (COCI17_ceste) C++17
160 / 160
 1467 ms 26148 KB 
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e3 + 5;
struct State {
	int node,sumT,sumC;
	bool operator< (const State &o) const {
		return (long long)sumT * sumC > (long long)o.sumT * o.sumC;
	}
};
bool done[MN];
set<pair<int,int>> monke[MN];
vector<array<int,3>> adj[MN];
int main() {
	int n,m;
	scanf ("%d %d",&n,&m);
	while (m--) {
		int a,b,t,c;
		scanf ("%d %d %d %d",&a,&b,&t,&c);
		adj[a].push_back({b,t,c});
		adj[b].push_back({a,t,c});
	}
	priority_queue<State> pq;
	pq.push({1,0,0}); monke[1] = {{0,0}};
	while (!pq.empty()) {
		State cur = pq.top(); pq.pop(); 
		for (auto [i,t,c] : adj[cur.node]) {
			int new_t = cur.sumT + t, new_c = cur.sumC + c;
			auto it = monke[i].upper_bound({new_t,1e9});
			if (it == monke[i].begin() || prev(it)->second > new_c) {
				monke[i].insert({new_t,new_c});
				pq.push({i,new_t,new_c});
			} 
		}
	}
	for (int i = 2; i <= n; i++) {
		long long ret = 1e18;
		for (auto [t,c] : monke[i]) ret = min(ret,(long long)t * c);
		printf ("%lld\n",ret == 1e18 ? -1 : ret);
	}
    return 0;
}

Compilation message

ceste.cpp: In function 'int main()':
ceste.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |  scanf ("%d %d",&n,&m);
      |  ~~~~~~^~~~~~~~~~~~~~~
ceste.cpp:18:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |   scanf ("%d %d %d %d",&a,&b,&t,&c);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1900 KB Output is correct
2 Correct 92 ms 2688 KB Output is correct
3 Correct 172 ms 2412 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 19092 KB Output is correct
2 Correct 1467 ms 14216 KB Output is correct
3 Correct 5 ms 876 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 5484 KB Output is correct
2 Correct 768 ms 18940 KB Output is correct
3 Correct 16 ms 1772 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 19948 KB Output is correct
2 Correct 478 ms 22436 KB Output is correct
3 Correct 450 ms 19748 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 21156 KB Output is correct
2 Correct 383 ms 19108 KB Output is correct
3 Correct 768 ms 26148 KB Output is correct