oj.uz

Submission #35802

# Submission time Handle Problem Language Result Execution time Memory
35802 2017-11-30T14:15:24 Z moonrabbit2 None (KOI16_gas) C++11
34 / 100
 1236 ms 37344 KB 
#include <bits/stdc++.h>
#define MAXV 3000
#define INF 1000000000
using namespace std;
typedef pair<int,int> P;
struct city
{
    int num;
    int cost;
};
int v,e,k;
int dist[MAXV][MAXV];
int ans[MAXV];
city cities[MAXV];
bool f(city a,city b)
{
    if(a.cost==b.cost)
        return a.num>b.num;
    return a.cost>b.cost;
}
int main()
{
    vector<pair<int,int>>graph[MAXV];
    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++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        graph[u-1].push_back(pair<int,int>(v-1,w));
        graph[v-1].push_back(pair<int,int>(u-1,w));
    }
    priority_queue<P,vector<P>,greater<P> >PQ;
    for(int k=0;k<v;k++){
        bool visit[MAXV];
        for(int i=0;i<v;i++)
            visit[i]=false;
        P t;
        t.first=0;
        t.second=k;
        PQ.push(t);
        for(int i=0;i<v;i++){
            P curr;
            while(!PQ.empty()){
                curr=PQ.top();
                PQ.pop();
                if(!visit[curr.second])
                    break;
            }
            visit[curr.second]=true;
            int ss=graph[curr.second].size();
            for(int j=0;j<ss;j++){
                if(dist[k][graph[curr.second][j].first]>dist[k][curr.second]+graph[curr.second][j].second){
                    dist[k][graph[curr.second][j].first]=dist[k][curr.second]+graph[curr.second][j].second;
                    t.first=dist[k][graph[curr.second][j].first];
                    t.second=graph[curr.second][j].first;
                    PQ.push(t);
                }
            }
        }
        while(!PQ.empty())
            PQ.pop();
    }
    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("%d",ans[v-1]);
    return 0;
}

Compilation message

gas.cpp: In function 'int main()':
gas.cpp:24: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:27: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:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&u,&v,&w);
                                   ^

Subtask #1
18.0 / 18.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 37344 KB Output is correct
2 Incorrect 286 ms 37344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 37344 KB Output is correct
2 Correct 966 ms 37344 KB Output is correct
3 Correct 953 ms 37344 KB Output is correct
4 Correct 949 ms 37344 KB Output is correct
5 Correct 983 ms 37344 KB Output is correct
6 Correct 1186 ms 37344 KB Output is correct
7 Correct 1229 ms 37344 KB Output is correct
8 Correct 1236 ms 37344 KB Output is correct
9 Correct 1116 ms 37344 KB Output is correct
10 Correct 1033 ms 37344 KB Output is correct
11 Correct 1049 ms 37344 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37212 KB Output is correct
2 Correct 0 ms 37212 KB Output is correct
3 Correct 0 ms 37212 KB Output is correct
4 Correct 0 ms 37212 KB Output is correct
5 Correct 0 ms 37212 KB Output is correct
6 Correct 0 ms 37212 KB Output is correct
7 Correct 0 ms 37212 KB Output is correct
8 Correct 0 ms 37212 KB Output is correct
9 Correct 0 ms 37212 KB Output is correct
10 Correct 0 ms 37212 KB Output is correct
11 Correct 0 ms 37212 KB Output is correct
12 Correct 0 ms 37212 KB Output is correct
13 Correct 0 ms 37212 KB Output is correct
14 Incorrect 13 ms 37212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37212 KB Output is correct
2 Correct 0 ms 37212 KB Output is correct
3 Correct 0 ms 37212 KB Output is correct
4 Correct 0 ms 37212 KB Output is correct
5 Correct 0 ms 37212 KB Output is correct
6 Correct 0 ms 37212 KB Output is correct
7 Correct 0 ms 37212 KB Output is correct
8 Correct 0 ms 37212 KB Output is correct
9 Correct 0 ms 37212 KB Output is correct
10 Correct 0 ms 37212 KB Output is correct
11 Correct 0 ms 37212 KB Output is correct
12 Correct 0 ms 37212 KB Output is correct
13 Correct 0 ms 37212 KB Output is correct
14 Correct 246 ms 37344 KB Output is correct
15 Incorrect 286 ms 37344 KB Output isn't correct
16 Halted 0 ms 0 KB -