Submission #51758

#	Time	Username	Problem	Language	Result	Execution time	Memory
51758		model_code	날다람쥐 (JOI14_ho_t4)	C++17	100 / 100	467 ms	30176 KiB

2014_ho_t4

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
const long long INF = 100001000010000100ll; // >> 10^9*10^5

int H[MAXN];
long long dist[MAXN];
vector<int> to[MAXN], cost[MAXN];

struct Dat{
	long long d;
	int v;
	Dat(long long d, int v):d(d),v(v){}
	bool operator<(const Dat& a)const{ return d < a.d;}
};

int main(){
	int N, M, X, A, B, T;
	scanf("%d%d%d",&N,&M,&X);
	
	for(int i = 1; i <= N; i++) scanf("%d",&H[i]);
	for(int i = 0; i < M; i++){
		scanf("%d%d%d",&A,&B,&T);
		to[A].push_back(B);
		cost[A].push_back(T);
		to[B].push_back(A);
		cost[B].push_back(T);
	}
	
	for(int i = 1; i <= N; i++) dist[i] = -INF;
	
	priority_queue<Dat> q;
	q.push(Dat(X,1));
	
	while(!q.empty()){
		Dat now = q.top(); q.pop();
		if(dist[now.v] != -INF) continue;
		dist[now.v] = now.d;
		for(int i = 0; i < to[now.v].size(); i++){
			int u = to[now.v][i], c = cost[now.v][i];
			if(c > H[now.v]) continue;
			q.push(Dat(min(now.d-c, (long long)H[u]), u));
		}
	}
	
	if(dist[N] == -INF) puts("-1");
	else printf("%lld\n",X+H[N]-dist[N]*2);
	
	return 0;
}

Compilation message (stderr)

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < to[now.v].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:22: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:24:35: 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:26: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: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50