oj.uz

답안 #701334

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701334 2023-02-21T01:03:23 Z Jasonwei08 두 로봇 (KOI18_robot) C++14
0 / 100
 47 ms 24156 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 4e5 + 10;

int n, m;
lint D[MAX];
vector<int> A;
vector<plint> G[MAX];
vector<pair<int, pint>> V[MAX];
int main() {
	cin.tie (0);
	ios_base::sync_with_stdio (0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c, p;
		cin >> a >> b >> c >> p;
		V[a].push_back ({ c, {p, b} });
		V[b].push_back ({ c, {p, a} });
	}
	int sz = n;
	for (int i = 1; i < n; i++) {
		if (V[i].empty()) continue;
		sort (V[i].begin(), V[i].end());
		for (int l = 0, r = 0; l < V[i].size(); l = r) {
			lint s = 0;
			while (r < V[i].size() && V[i][l].va == V[i][r].va) s += V[i][r++].vb.va;
			if (r - l == 1) G[i].emplace_back (0, V[i][l].vb.vb);
			else {
				G[i].emplace_back (0, ++sz);
				for (int j = l; j < r; j++) {
					pint x = V[i][j].vb;
					G[i].emplace_back  (x);
					G[x.vb].emplace_back (0, sz);
					G[sz].emplace_back (s - x.va, x.vb);
				}
			}
		}
	}
	priority_queue<plint> Q;
	Q.emplace (0, 1);
	for (int i = 1; i <= sz; i++) D[i] = 4e18;
	while (!Q.empty()) {
		auto t = Q.top();
		Q.pop();
		if (D[t.vb] != 4e18) continue;
		D[t.vb] = -t.va;
		for (auto nxt : G[t.vb]) Q.emplace (t.va - nxt.va, nxt.vb);
	}
	cout << (D[n] == 4e18 ? -1 : D[n]);
}

Compilation message

robot.cpp: In function 'int main()':
robot.cpp:29:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (int l = 0, r = 0; l < V[i].size(); l = r) {
      |                          ~~^~~~~~~~~~~~~
robot.cpp:31:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    while (r < V[i].size() && V[i][l].va == V[i][r].va) s += V[i][r++].vb.va;
      |           ~~^~~~~~~~~~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 19796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 21460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 24156 KB Output isn't correct
2 Halted 0 ms 0 KB -