結果

提出番号	1787
提出者	ecasdqina
言語	C++
提出日時	2018-08-04 13:52:59
問題名	(73)観光計画
結果	AC
点数	100%

---

テストケース

ソースコード

#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

std::vector<std::vector<std::pair<int, int>>> g;
int n, m, k;

int solve() {
	std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> qu;
	std::vector<i64> min_cost(n + 1, 1e18);
	qu.push({1e9, n});
	
	while(!qu.empty()) {
		auto p = qu.top(); qu.pop();
		
		for(auto e : g[p.second]) {
			if(e.second + p.first >= min_cost[e.first]) continue;
			min_cost[e.first] = e.second + p.first;
			qu.push({min_cost[e.first], e.first});
		}
	}
	
	int c = 0;
	for(int i = 0; i < n; i++) if(min_cost[i] <= 1e9) c++;
	return c;
}

int main(){
	cin >> n >> m >> k; g.resize(n + 1);
	for(int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		
		g[a - 1].push_back({b - 1, c});
		g[b - 1].push_back({a - 1, c});
	}
	for(int i = 0; i < k; i++) {
		int a, c; cin >> a >> c;
		
		g[n].push_back({a - 1, -c});
	}
	
	cout << solve() << endl;
	return 0;
}