Submission #41116

#	Time	Username	Problem	Language	Result	Execution time	Memory
41116		14kg	주유소 (KOI16_gas)	C++11	100 / 100	51 ms	51904 KiB

gas

#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
#define INF 999999999999999999
#define min2(x,y) (x<y?x:y)

using namespace std;
typedef pair<long long, pair<int, int> > pip;
int n, in[2501];
long long d[2501][2501];
vector<pair<int, int> > r[2501];
priority_queue<pip, vector<pip>, greater<pip> > Q;

int main() {
	int m, x, y, z;
	pip t;

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &in[i]);
	while (m--) {
		scanf("%d %d %d", &x, &y, &z);
		r[x].push_back({ y,z }), r[y].push_back({ x,z });
	}

	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= 2500; j++) d[i][j] = INF;
	
	Q.push({ 0,{1,2500} });
	while (!Q.empty()) {
		t = Q.top(), Q.pop();

		if (t.second.first == n) {
			printf("%lld", t.first);
			return 0;
		}

		t.second.second = min2(t.second.second, in[t.second.first]);
		for(auto i:r[t.second.first])
			if (d[i.first][t.second.second] > t.first + t.second.second*i.second) {
				d[i.first][t.second.second] = t.first + t.second.second*i.second;
				Q.push({ d[i.first][t.second.second],{i.first,t.second.second} });
			}
	}
}

Compilation message (stderr)

gas.cpp: In function 'int main()':
gas.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
gas.cpp:20:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d", &in[i]);
                                                  ^
gas.cpp:22:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
                                ^

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