Submission #20639

#	Time	Username	Problem	Language	Result	Execution time	Memory
20639		model_code	주유소 (KOI16_gas)	C++11	100 / 100	1366 ms	50436 KiB

gas

#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);
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 (stderr)

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);
                                           ^

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