QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116670#6523. Escape PlanITMO_pengzoo#WA 937ms41692kbC++205.1kb2023-06-29 18:55:222023-06-29 18:55:24

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-29 18:55:24]
  • 评测
  • 测评结果:WA
  • 用时:937ms
  • 内存:41692kb
  • [2023-06-29 18:55:22]
  • 提交

answer

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <stdio.h>
#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
    #define debug(x) 238
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"

using ll = long long;
using ld = long double;

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}

template<size_t index, typename T>
std::ostream& print_tuple(std::ostream& out, const T& t) {
    if constexpr (index == std::tuple_size<T>::value) {
        out << ")";
        return out;
    } else {
        if (index > 0) {
            out << ", ";
        } else {
            out << "(";
        }
        out << std::get<index>(t);
        return print_tuple<index + 1, T>(out, t);
    }
}

template<typename ...T>
std::ostream& operator<<(std::ostream& out, const std::tuple<T...>& t) {
    return print_tuple<0, std::tuple<T...>>(out, t);
}

template<typename Container, typename = decltype(std::begin(std::declval<Container>()))>
typename std::enable_if<!std::is_same<Container, std::string>::value, std::ostream&>::type
operator<<(std::ostream& out, const Container& container) {
    out << "{";
    for (auto it = container.begin(); it != container.end(); ++it) {
        if (it != container.begin()) {
            out << ", ";
        }
        out << *it;
    }
    out << "}";
    return out;
}

template<typename T>
bool smin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool smax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 100100;

std::vector<std::pair<int, int>> g[N];
int monsters[N];
std::priority_queue<ll> heaps[N];
ll dist[N];

class Comparator {
public:
	bool operator()(int i1, int i2) const {
		ll val1 = heaps[i1].top();
		ll val2 = heaps[i2].top();
		return val1 < val2 || (val1 == val2 && i1 < i2);
	}
};

void solve() {
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);

	for (int i = 0; i < n; ++i) {
		g[i].clear();
		while (!heaps[i].empty()) {
			heaps[i].pop();
		}
		dist[i] = LINF;
	}

	std::vector<int> exits(k);
	for (int i = 0; i < k; ++i) {
		scanf("%d", &exits[i]);
		--exits[i];
	}
	for (int i = 0; i < n; ++i) {
		scanf("%d", &monsters[i]);
	}

	for (int i = 0; i < m; ++i) {
		int from, to, cost;
		scanf("%d%d%d", &from, &to, &cost);

		g[from - 1].emplace_back(to - 1, cost);
		g[to - 1].emplace_back(from - 1, cost);
	}
	for (auto i : exits) {
		monsters[i] = 0;
	}
	for (int i = 0; i < n; ++i) {
		smin(monsters[i], (int)g[i].size());
		for (int j = 0; j < monsters[i] + 1; ++j) {
			heaps[i].push(LINF);
		}
	}
	for (auto i : exits) {
		while (!heaps[i].empty()) {
			heaps[i].pop();
		}
		heaps[i].push(0);
	}

	std::set<int, Comparator> setik;
	auto update = [&](int v, ll d) {
		// std::cout << "Updating " << v << ' ' << d << std::endl;
		if (heaps[v].top() <= d) {
			return;
		}
		bool fl = setik.find(v) != setik.end();
		if (fl) {
			setik.erase(v);
		}
		heaps[v].pop();
		heaps[v].push(d);
		if (fl) {
			setik.insert(v);
		}
	};

	for (int i = 0; i < k; ++i) {
		int cur = exits[i];
		update(cur, 0);
		dist[cur] = 0;
		setik.insert(cur);
	}

	while (!setik.empty()) {
		int v = *setik.begin();
		setik.erase(setik.begin());
		// debug(v);
		// debug(dist[v]);
		// debug(heaps[v].size());
		// debug(heaps[v].top());
		assert(dist[v] != LINF);
		assert(heaps[v].top() != LINF);
		assert(heaps[v].top() >= dist[v]);

		for (auto[to, cost] : g[v]) {
			if (dist[v] + cost < dist[to]) {
				update(to, dist[v] + cost);
				if (heaps[to].top() != LINF) {
					setik.insert(to);
					dist[to] = dist[v] + cost;
				}
			}
		}
	}

	if (dist[0] == LINF) {
		printf("-1\n");
	} else {
		printf("%lld\n", dist[0]);
	}
}

void run() {
	int t;
	scanf("%d", &t);

	while (t--) {
		solve();
	}    
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    #ifdef PERVEEVM_LOCAL
        auto start = std::chrono::high_resolution_clock::now();
    #endif

    run();

    #ifdef PERVEEVM_LOCAL
        auto end = std::chrono::high_resolution_clock::now();
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9528kb

input:

2
3 4 1
3
1 1 1
1 2 1
1 2 2
2 3 1
2 3 2
3 2 2
2 3
2 0 0
1 2 1
1 3 1

output:

4
-1

result:

ok 2 number(s): "4 -1"

Test #2:

score: -100
Wrong Answer
time: 937ms
memory: 41692kb

input:

100
100 1808 2
94 47
3 3 0 2 4 3 3 4 0 0 2 2 2 3 2 4 0 2 3 4 4 2 0 3 4 3 1 0 2 1 2 2 0 3 4 4 4 1 2 2 3 1 0 0 3 1 4 2 1 3 3 4 3 0 4 1 0 3 2 1 4 4 1 3 2 3 3 3 3 1 0 3 0 4 3 1 0 4 0 4 4 1 2 0 0 4 1 3 3 3 0 2 2 1 1 2 3 4 1 2
72 29 1138
59 78 2398
95 5 1610
32 46 4176
36 99 8143
100 69 413
61 58 1595
9 9...

output:

3376
429
1339
2010
1432
1445
331
3207
670
923
1083
837
360
1114
741
2893
223
1138
1353
658
3186
1751
425
1694
2247
10728
842
2322
436
628
1788
490
651
-1
765
6265
507
1445
613
678
402
3769
12802
4341
4320
1953
-1
510
729
2792
-1
913
773
1907
990
557
2446
270
1251
485
1384
954
1472
1295
516
2882
938
...

result:

wrong answer 1st numbers differ - expected: '5109', found: '3376'