| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 35806 | moonrabbit2 | 주유소 (KOI16_gas) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MAXV 2500
#define INF 100000000000
using namespace std;
typedef pair<long long,int> P;
struct city
{
int num;
int cost;
};
vector<pair<int,long long>>graph[MAXV];
int v,e.uu,vv,ww;
long long dist[MAXV][MAXV];
long long ans[MAXV];
city cities[MAXV];
priority_queue<P,vector<P>,greater<P>>PQ;
bool f(city a,city b)
{
if(a.cost==b.cost)
return a.num<b.num;
return a.cost>b.cost;
}
int main()
{
scanf("%d %d",&v,&e);
for(int i=0;i<v;i++){
cities[i].num=i;
scanf("%d",&cities[i].cost);
}
for(int i=0;i<v;i++){
for(int j=0;j<v;j++){
if(i!=j)
dist[i][j]=INF;
}
}
for(int i=0;i<e;i++){
scanf("%d %d %d",&uu,&vv,&ww);
uu--;vv--;
graph[uu].push_back(P(vv,(long long)w));
graph[vv].push_back(P(uu,(long long)w));
}
for(int k=0;k<v;k++){
bool visit[MAXV];
PQ.push(P(0,k));
P tp;
while(!PQ.empty()){
tp=PQ.top();
PQ.pop();
if(dist[k][tp.second]<tp.first)
continue;
for(int j=0;j<graph[tp.second].size();j++){
if(dist[k][graph[tp.second][j].first]>dist[k][tp.second]+graph[tp.second][j].second){
dist[k][graph[tp.second][j].first]=dist[k][tp.second]+graph[tp.second][j].second;
P t;
t.first=dist[k][graph[tp.second][j].first];
t.second=graph[tp.second][j].first;
PQ.push(t);
}
}
}
}
sort(cities+1,cities+v-1,f);
for(int i=1;i<v;i++){
ans[cities[i].num]=INF;
for(int j=0;j<i;j++){
ans[cities[i].num]=min(ans[cities[i].num],ans[cities[j].num]+dist[cities[j].num][cities[i].num]*cities[j].cost);
}
}
printf("%lld",ans[v-1]);
return 0;
}