oj.uz

Submission #366714

# Submission time Handle Problem Language Result Execution time Memory
366714 2021-02-15T07:22:01 Z ChrisT Ceste (COCI17_ceste) C++17
96 / 160
 400 ms 21028 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++) {
		int ret = 1e9;
		for (auto [t,c] : monke[i]) ret = min(ret,t * c);
		printf ("%d\n",ret == 1e9 ? -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 500 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 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 660 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 4 ms 620 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1904 KB Output is correct
2 Correct 89 ms 2772 KB Output is correct
3 Correct 165 ms 2412 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 19128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 5612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 20076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 400 ms 21028 KB Output isn't correct
2 Halted 0 ms 0 KB -