Submission #35808

#	Time	Username	Problem	Language	Result	Execution time	Memory
35808		moonrabbit2	주유소 (KOI16_gas)	C++11	100 / 100	1366 ms	51208 KiB

gas

#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)ww));
        graph[vv].push_back(P(uu,(long long)ww));
    }
    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;
}

Compilation message (stderr)

gas.cpp: In function 'int main()':
gas.cpp:51:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<graph[tp.second].size();j++){
                          ^
gas.cpp:43:14: warning: unused variable 'visit' [-Wunused-variable]
         bool visit[MAXV];
              ^
gas.cpp:25:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&v,&e);
                         ^
gas.cpp:28:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&cities[i].cost);
                                    ^
gas.cpp:37:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&uu,&vv,&ww);
                                      ^

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