Submission #366715

#	Time	Username	Problem	Language	Result	Execution time	Memory
366715		ChrisT	Ceste (COCI17_ceste)	C++17	160 / 160	1467 ms	26148 KiB

ceste

#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 (stderr)

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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16