oj.uz

Submission #153952

# Submission time Handle Problem Language Result Execution time Memory
153952 2019-09-17T14:51:24 Z mhy908 None (JOI14_ho_t4) C++14
0 / 100
 2000 ms 262144 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define llinf 8987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

int h[100010];
LL dist[100010];
vector<int> link[100010], c[100010];
int n, m, x;

int main(){
	scanf("%d %d %d",&n, &m, &x);
	for(int i=1; i<=n; i++) scanf("%d", &h[i]);
	for(int i=1; i<=m; i++){
        int a, b, t;
		scanf("%d %d %d", &a, &b, &t);
		if(h[a]>=t){
            link[a].pb(b);
            c[a].pb(t);
		}
		if(h[b]>=t){
            link[b].pb(a);
            c[b].pb(t);
		}
	}
	for(int i=1; i<=n; i++)dist[i]=-llinf;
	priority_queue<pair<LL, int> > q;
	q.push({-(LL)x, -1});
	while(!q.empty()){
		int now=-q.top().S;
		LL dis=-q.top().F;
		q.pop();
		if(dist[now]>=dis)continue;
		for(int i=0; i<link[now].size(); i++){
			int u=link[now][i], co=c[now][i];
			//printf("%lld %d\n", min(dis-co, (LL)h[u]), u);
			q.push({-min(dis-co, (LL)h[u]), -u});
		}
	}
    //for(int i=1; i<=n; i++)printf("%lld ", dist[i]);
	if(dist[n]==-llinf)puts("-1");
	else printf("%lld", x+h[n]-dist[n]*2);
}

Compilation message

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<link[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n, &m, &x);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d", &h[i]);
                          ~~~~~^~~~~~~~~~~~~
2014_ho_t4.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2040 ms 5112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2040 ms 5112 KB Time limit exceeded
2 Halted 0 ms 0 KB -