oj.uz

Submission #20641

# Submission time Handle Problem Language Result Execution time Memory
20641 2017-02-13T06:18:56 Z model_code None (KOI16_gas) C++11
0 / 100
 353 ms 50300 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

FILE *fp1 = stdin;
FILE *fp2 = stdout;

#define V 2500
#define INF 0x7fffffffffffffff
#define min2(x,y) ((x)<(y)?(x):(y))

int n, m;
int oil_v[V + 1];
vector<int> go[V + 1], d[V + 1];
long long shortest_d[V + 1][V + 1];
priority_queue< pair<int, long long>, vector<pair<int, long long> >, greater<pair<int, long long> > > q;

void input(void) {
int i;
int v1, v2, weight;
fscanf(fp1, "%d %d", &n, &m);
for (i = 1; i <= n; i++)
fscanf(fp1, "%d", &oil_v[i]);
for (i = 1; i <= m; i++) {
fscanf(fp1, "%d %d %d", &v1, &v2, &weight);weight+=1;
go[v1].push_back(v2);
d[v1].push_back(weight);
  go[v2].push_back(v1);
d[v2].push_back(weight);
}
}
void dijkstra(int start) {
int i, j, size_p;
bool check[V + 1];
pair<int, long long> t, tt;

for (i = 1; i <= n; i++)check[i] = false;

tt.first = 0; tt.second = start;
q.push(tt);
  for (i = 1; i <= n; i++) {
while (!q.empty()) {
t = q.top(); q.pop();
if (!check[t.second]) break;
}
check[t.second] = true;
size_p = go[t.second].size();
for (j = 0; j<size_p; j++) {
if (shortest_d[start][go[t.second][j]] > shortest_d[start][t.second] + oil_v[start] * d[t.second][j]) {
shortest_d[start][go[t.second][j]] = shortest_d[start][t.second] + oil_v[start] * d[t.second][j];
tt.first = shortest_d[start][go[t.second][j]];
tt.second = go[t.second][j];
q.push(tt);
}
}
}
while (!q.empty()) q.pop();
}
long long get_answer(void) {
int i, j, ii, jj;
pair<int, int> sorted_oil_v[V + 1];
long long min_cost[V + 1];

for (i = 1; i <= n; i++) {
sorted_oil_v[i].first = -oil_v[i];
sorted_oil_v[i].second = i;
}
sort(sorted_oil_v + 2, sorted_oil_v + n);

min_cost[1] = 0;
for (i = 2; i <= n; i++) {
ii = sorted_oil_v[i].second;
min_cost[ii] = INF;
for (j = 1; j<i; j++) {
jj = sorted_oil_v[j].second;
min_cost[ii] = min2(min_cost[ii], min_cost[jj] + shortest_d[jj][ii]);
}
}

return min_cost[n];
}
int main(void) {
int i, j;

input();

for (i = 1; i<n; i++) {
for (j = i + 1; j <= n; j++) {
shortest_d[i][j] = shortest_d[j][i] = INF;
}
dijkstra(i);
}

fprintf(fp2, "%lld\n", get_answer());
return 0;
}

Compilation message

gas.cpp: In function 'void input()':
gas.cpp:24:29: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 fscanf(fp1, "%d %d", &n, &m);
                             ^
gas.cpp:26:29: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 fscanf(fp1, "%d", &oil_v[i]);
                             ^
gas.cpp:28:43: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 fscanf(fp1, "%d %d %d", &v1, &v2, &weight);weight+=1;
                                           ^

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 50168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 329 ms 50300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 353 ms 50300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 50168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 50168 KB Output isn't correct
2 Halted 0 ms 0 KB -