結果

提出番号 1426
提出者 olphe
言語 C++
提出日時 2018-08-02 23:06:28
問題名 (73)観光計画
結果 WA
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 WA 0% 45ms 30528KB
2 WA 0% 42ms 35040KB
3 WA 0% 22ms 21136KB
4 WA 0% 72ms 44016KB
5 WA 0% 40ms 26432KB
6 WA 0% 55ms 39760KB
7 WA 0% 68ms 42944KB
8 WA 0% 61ms 44000KB
9 WA 0% 26ms 24656KB
10 WA 0% 69ms 50688KB
11 WA 0% 38ms 27328KB
12 WA 0% 11ms 16576KB
13 WA 0% 26ms 28704KB
14 WA 0% 80ms 47856KB
15 WA 0% 53ms 37984KB
16 WA 0% 55ms 38544KB
17 WA 0% 60ms 43760KB
18 WA 0% 49ms 33792KB
19 WA 0% 12ms 15216KB
20 WA 0% 33ms 29904KB
21 WA 0% 20ms 20144KB
22 WA 0% 34ms 25904KB
23 WA 0% 29ms 27328KB
24 WA 0% 80ms 58608KB
25 WA 0% 58ms 43120KB
26 WA 0% 64ms 48640KB
27 WA 0% 23ms 18512KB
28 WA 0% 22ms 17136KB
29 WA 0% 41ms 33296KB
30 WA 0% 31ms 28608KB
31 WA 0% 88ms 52448KB
32 WA 0% 52ms 35984KB
33 WA 0% 11ms 11968KB
34 WA 0% 73ms 46240KB
35 WA 0% 11ms 12128KB
36 WA 0% 65ms 44432KB
37 WA 0% 32ms 24416KB
38 WA 0% 8ms 9792KB
39 WA 0% 75ms 57120KB
40 WA 0% 11ms 15920KB
41 WA 0% 81ms 49552KB
42 WA 0% 21ms 18304KB
43 WA 0% 89ms 53520KB
44 WA 0% 50ms 34576KB
45 WA 0% 42ms 36496KB
46 WA 0% 64ms 38704KB
47 WA 0% 78ms 51984KB
48 WA 0% 81ms 52304KB
49 WA 0% 48ms 33872KB
50 WA 0% 52ms 45008KB
51 WA 0% 20ms 16256KB
52 WA 0% 37ms 30704KB
53 WA 0% 21ms 19296KB
54 WA 0% 50ms 40064KB
55 WA 0% 15ms 16960KB
56 WA 0% 45ms 35744KB
57 WA 0% 22ms 26496KB
58 WA 0% 31ms 24208KB
59 WA 0% 18ms 17264KB
60 WA 0% 21ms 20512KB
61 WA 0% 33ms 24944KB
62 WA 0% 56ms 43472KB
63 WA 0% 53ms 41664KB
64 WA 0% 74ms 45008KB
65 WA 0% 64ms 43152KB
66 WA 0% 3ms 8528KB
67 WA 0% 29ms 30240KB
68 WA 0% 39ms 35568KB
69 WA 0% 95ms 61360KB
70 WA 0% 43ms 36640KB

ソースコード

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 1e-8;

long long int N, M, K, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M >> K;
	vector<vector<pair<int, long long int>>>edge(N + 1);
	for (int i = 0; i < M; i++) {
		cin >> L >> R >> H;
		L;
		R;
		edge[L].push_back({ R,K });
		edge[R].push_back({ L,K });
	}
	for (int i = 0; i < K; i++) {
		cin >> L >> R;
		edge[0].push_back({ L,MOD - R });
	}
	vector<long long int>dis(N + 1, MOD*MOD);
	dis[0] = 0;
	set<pair<long long int, int>>s;
	while (!s.empty()) {
		auto c = *s.begin();
		s.erase(s.begin());
		int cn = c.second;
		long long int cc = c.first;
		for (auto i : edge[cn]) {
			if (dis[i.first] > cc + i.second) {
				dis[i.first] = cc + i.second;
				s.insert({ dis[i.first],i.first });
			}
		}
	}
	int ans = 0;
	for (auto i : dis) {
		if (i <= MOD) {
			ans++;
		}
	}
	cout << ans - 1 << endl;
	return 0;
}