Submission #430300

#	Time	Username	Problem	Language	Result	Execution time	Memory
430300		Nicholas_Patrick	Treatment Project (JOI20_treatment)	C++17	35 / 100	3067 ms	2620 KiB

treatment

#include <cstdio>
#include <queue>
using namespace std;

template <typename T>
using eueuq_ytiroirp = priority_queue<T, vector<T>, greater<T>>;
struct node{
	int l, r, t, c;
	// node(int l, int r, int t, int c):l(l-1), r(r), t(t), c(c){}
	bool connect(node rhs)const{
		return t<rhs.t?
			rhs.l<=r-rhs.t+t:
			rhs.l<=r-t+rhs.t;
	}
};
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	long long ans=1000000000000000;
	vector<node> nodes(m);
	for(auto& i : nodes)
		scanf("%d%d%d%d", &i.t, &i.l, &i.r, &i.c), i.l--;
	vector<long long> dist(m, ans);
	vector<bool> explored(m, false);

	for(int i=0; i<m; i++){
		if(nodes[i].l==0)
			dist[i]=nodes[i].c;
	}
	for(int i=0; i<m; i++){
		int from=-1;
		for(int j=0; j<m; j++){
			if(explored[j])
				continue;
			if(from==-1 or dist[from]>dist[j])
				from=j;
		}
		explored[from]=true;
		for(int j=0; j<m; j++){
			if(explored[j])
				continue;
			if(nodes[from].connect(nodes[j]))
				dist[j]=min(dist[j], dist[from]+nodes[j].c);
		}
	}

	for(int i=0; i<m; i++){
		if(nodes[i].r==n)
			ans=min(ans, dist[i]);
	}
	if(ans==1000000000000000)
		ans=-1;
	printf("%lld\n", ans);
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
treatment.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d%d%d%d", &i.t, &i.l, &i.r, &i.c), i.l--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61