Submission #207053

#	Time	Username	Problem	Language	Result	Execution time	Memory
207053		Pentagon	주유소 (KOI16_gas)	C++14	100 / 100	909 ms	26232 KiB

gas

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue> 
using namespace std;
//Real Problem
int n,m,prc[2600],a,b,w;
long long DT[2600];
vector<int> arr;
bool cmp(int a,int b){
	if(prc[a]==prc[b])
		return a<b;
	return prc[a]<prc[b];
}
//for Dijkstra
int dis[2600][2600],INF=1e9;
struct node{
	int num,d;
	bool operator <(const node& tmp) const{
		return d>tmp.d;
	}
};
vector<vector<node> > v;
priority_queue<node> pq;
void Dijkstra(int s,int D[]){
	fill(D+1,D+n+1,INF);
	D[s]=0; pq.push(node{s,0});
	while(!pq.empty()){
		auto cur=pq.top(); pq.pop();
		if(cur.d>D[cur.num]) continue;
		for(auto&next : v[cur.num]){
			if(cur.d+next.d>=D[next.num]) continue;
			D[next.num]=D[cur.num]+next.d;
			pq.push(node{next.num,D[next.num]});
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) arr.push_back(i),scanf("%d",prc+i);
	v.resize(n+1);
	while(m--){
		scanf("%d%d%d",&a,&b,&w);
		v[a].push_back(node{b,w});
		v[b].push_back(node{a,w});
	}
	for(int i=1;i<=n;i++) Dijkstra(i,dis[i]);
	sort(arr.begin(),arr.end(),cmp);
	for(int i=0;i<n;i++){
		int k=arr[i];
		DT[k]=1LL*dis[k][n]*prc[k];
		for(int j=0;j<i;j++){
			int k2=arr[j];
			DT[k]=min(DT[k],1LL*dis[k][k2]*prc[k]+DT[k2]);
		}
		if(arr[i]==1) break;
	}
	printf("%lld",DT[1]);
}

Compilation message (stderr)

gas.cpp: In function 'int main()':
gas.cpp:39: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:40:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) arr.push_back(i),scanf("%d",prc+i);
                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
gas.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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