oj.uz

Submission #35808

# Submission time Handle Problem Language Result Execution time Memory
35808 2017-11-30T14:43:53 Z moonrabbit2 None (KOI16_gas) C++11
100 / 100
 1366 ms 51208 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 50944 KB Output is correct
2 Correct 0 ms 50944 KB Output is correct
3 Correct 0 ms 50944 KB Output is correct
4 Correct 0 ms 50944 KB Output is correct
5 Correct 0 ms 50944 KB Output is correct
6 Correct 0 ms 50944 KB Output is correct
7 Correct 0 ms 50944 KB Output is correct
8 Correct 0 ms 50944 KB Output is correct
9 Correct 0 ms 50944 KB Output is correct
10 Correct 0 ms 50944 KB Output is correct
11 Correct 0 ms 50944 KB Output is correct
12 Correct 0 ms 50944 KB Output is correct
13 Correct 0 ms 50944 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 51076 KB Output is correct
2 Correct 303 ms 51076 KB Output is correct
3 Correct 293 ms 51076 KB Output is correct
4 Correct 309 ms 51076 KB Output is correct
5 Correct 286 ms 51076 KB Output is correct
6 Correct 313 ms 51076 KB Output is correct
7 Correct 296 ms 51076 KB Output is correct
8 Correct 289 ms 51076 KB Output is correct
9 Correct 289 ms 51076 KB Output is correct
10 Correct 279 ms 51076 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 51076 KB Output is correct
2 Correct 1209 ms 51208 KB Output is correct
3 Correct 1156 ms 51208 KB Output is correct
4 Correct 1083 ms 51208 KB Output is correct
5 Correct 1103 ms 51208 KB Output is correct
6 Correct 1366 ms 51208 KB Output is correct
7 Correct 1319 ms 51208 KB Output is correct
8 Correct 1353 ms 51208 KB Output is correct
9 Correct 1169 ms 51208 KB Output is correct
10 Correct 1159 ms 51208 KB Output is correct
11 Correct 1123 ms 51208 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 50944 KB Output is correct
2 Correct 0 ms 50944 KB Output is correct
3 Correct 0 ms 50944 KB Output is correct
4 Correct 0 ms 50944 KB Output is correct
5 Correct 0 ms 50944 KB Output is correct
6 Correct 0 ms 50944 KB Output is correct
7 Correct 0 ms 50944 KB Output is correct
8 Correct 0 ms 50944 KB Output is correct
9 Correct 0 ms 50944 KB Output is correct
10 Correct 0 ms 50944 KB Output is correct
11 Correct 0 ms 50944 KB Output is correct
12 Correct 0 ms 50944 KB Output is correct
13 Correct 0 ms 50944 KB Output is correct
14 Correct 16 ms 50944 KB Output is correct
15 Correct 19 ms 50944 KB Output is correct
16 Correct 13 ms 50944 KB Output is correct
17 Correct 69 ms 51076 KB Output is correct
18 Correct 76 ms 51076 KB Output is correct
19 Correct 29 ms 50944 KB Output is correct
20 Correct 29 ms 50944 KB Output is correct
21 Correct 29 ms 50944 KB Output is correct
22 Correct 26 ms 50944 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 50944 KB Output is correct
2 Correct 0 ms 50944 KB Output is correct
3 Correct 0 ms 50944 KB Output is correct
4 Correct 0 ms 50944 KB Output is correct
5 Correct 0 ms 50944 KB Output is correct
6 Correct 0 ms 50944 KB Output is correct
7 Correct 0 ms 50944 KB Output is correct
8 Correct 0 ms 50944 KB Output is correct
9 Correct 0 ms 50944 KB Output is correct
10 Correct 0 ms 50944 KB Output is correct
11 Correct 0 ms 50944 KB Output is correct
12 Correct 0 ms 50944 KB Output is correct
13 Correct 0 ms 50944 KB Output is correct
14 Correct 253 ms 51076 KB Output is correct
15 Correct 303 ms 51076 KB Output is correct
16 Correct 293 ms 51076 KB Output is correct
17 Correct 309 ms 51076 KB Output is correct
18 Correct 286 ms 51076 KB Output is correct
19 Correct 313 ms 51076 KB Output is correct
20 Correct 296 ms 51076 KB Output is correct
21 Correct 289 ms 51076 KB Output is correct
22 Correct 289 ms 51076 KB Output is correct
23 Correct 279 ms 51076 KB Output is correct
24 Correct 236 ms 51076 KB Output is correct
25 Correct 1209 ms 51208 KB Output is correct
26 Correct 1156 ms 51208 KB Output is correct
27 Correct 1083 ms 51208 KB Output is correct
28 Correct 1103 ms 51208 KB Output is correct
29 Correct 1366 ms 51208 KB Output is correct
30 Correct 1319 ms 51208 KB Output is correct
31 Correct 1353 ms 51208 KB Output is correct
32 Correct 1169 ms 51208 KB Output is correct
33 Correct 1159 ms 51208 KB Output is correct
34 Correct 1123 ms 51208 KB Output is correct
35 Correct 16 ms 50944 KB Output is correct
36 Correct 19 ms 50944 KB Output is correct
37 Correct 13 ms 50944 KB Output is correct
38 Correct 69 ms 51076 KB Output is correct
39 Correct 76 ms 51076 KB Output is correct
40 Correct 29 ms 50944 KB Output is correct
41 Correct 29 ms 50944 KB Output is correct
42 Correct 29 ms 50944 KB Output is correct
43 Correct 26 ms 50944 KB Output is correct
44 Correct 429 ms 51076 KB Output is correct
45 Correct 556 ms 51076 KB Output is correct
46 Correct 636 ms 51076 KB Output is correct
47 Correct 1103 ms 51208 KB Output is correct
48 Correct 1176 ms 51208 KB Output is correct
49 Correct 936 ms 51208 KB Output is correct
50 Correct 973 ms 51208 KB Output is correct
51 Correct 983 ms 51208 KB Output is correct
52 Correct 1086 ms 51208 KB Output is correct