Submission #57063

#	Time	Username	Problem	Language	Result	Execution time	Memory
57063		dennisstar	주유소 (KOI16_gas)	C++11	100 / 100	1952 ms	27440 KiB

gas

#include <bits/stdc++.h>
#define mkp(a,b) make_pair(a,b)
typedef long long LL;
using namespace std;
int N,M;
int P[2510];
int dist[2510][2510]; long long Dp[2510];
vector<int> R[2510], D[2510];
int arr[2510];
bool cmp(int a, int b){return P[a]>P[b];}
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > PQ;
int chk[2510];
void djk(int lev)
{
	memset(chk, 0, sizeof(chk));
	while(!PQ.empty()) PQ.pop();
	PQ.push(mkp(0,lev));
	int lv, i, ds;
	while(!PQ.empty()) {
		ds=PQ.top().first;
		lv=PQ.top().second;
		PQ.pop();
		if (chk[lv]) continue;
		dist[lev][lv]=ds;
		chk[lv]=1;
		for (i=0; i<R[lv].size(); i++) {
			if(chk[R[lv][i]]) continue;
			PQ.push(mkp(ds+D[lv][i],R[lv][i]));
		}
	}
}
int main()
{
	scanf("%d %d", &N, &M);
	int i, j, k, x, y;
	for (i=1; i<=N; i++) scanf("%d",&P[i]);
	for (i=0; i<M; i++) {
		scanf("%d %d %d", &x, &y, &j);
		R[x].push_back(y);
		R[y].push_back(x);
		D[x].push_back(j);
		D[y].push_back(j);
	}
	for (i=1; i<=N; i++) arr[i]=i;
	for (i=1; i<=N; i++) djk(i);
	sort(arr+2,arr+N,cmp);
	for (j=2; P[arr[j]]>=P[1]&&j<N; ) j++;
	for (i=j; i<=N; i++) {
		Dp[arr[i]]=(LL)P[1]*(LL)dist[1][arr[i]];
		for (k=j; k<i; k++) {
			Dp[arr[i]]=std::min(Dp[arr[i]], Dp[arr[k]]+(LL)P[arr[k]]*dist[arr[k]][arr[i]]);
		}
	}
	printf("%lld", Dp[N]);
	return 0;
}

Compilation message (stderr)

gas.cpp: In function 'void djk(int)':
gas.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i=0; i<R[lv].size(); i++) {
             ~^~~~~~~~~~~~~
gas.cpp: In function 'int main()':
gas.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
gas.cpp:36:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=1; i<=N; i++) scanf("%d",&P[i]);
                       ~~~~~^~~~~~~~~~~~
gas.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &j);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27