fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<ll, ll> pll;
  5. ll N, M, K, dist[100005];
  6. vector<pll> vt[100005];
  7. vector<int> vtt;
  8. struct info {
  9. 	ll n, d;
  10. 	bool operator < (const info& a) const {
  11. 		return d > a.d;
  12. 	}
  13. };
  14. priority_queue<info> pq;
  15. int main() {
  16. 	ios::sync_with_stdio(0);
  17. 	cin.tie(0); cout.tie(0);
  18. 	cin >> N >> M >> K;
  19. 	for (int i = 1, a, b, c; i <= M; i++) {
  20. 		cin >> a >> b >> c;
  21. 		vt[b].push_back({ a,c });
  22. 	}
  23. 	for (int i = 1; i <= N; i++) dist[i] = 1e18;
  24. 	for (int i = 1, a; i <= K; i++) {
  25. 		cin >> a;
  26. 		vtt.push_back(a);
  27. 		dist[a] = 0;
  28. 		pq.push({ a,0 });
  29. 	}
  30. 	while (!pq.empty()) {
  31. 		info p = pq.top(); pq.pop();
  32. 		if (p.d != dist[p.n]) continue;
  33. 		ll n = p.n;
  34. 		for (pll pp : vt[n]) {
  35. 			ll nn = pp.first, dd = pp.second;
  36. 			if (dist[nn] > dist[n] + dd) {
  37. 				dist[nn] = dist[n] + dd;
  38. 				pq.push({ nn,dist[nn] });
  39. 			}
  40. 		}
  41. 	}
  42. 	ll maxV = -1, ans = 0;
  43. 	for (int i = 1; i <= N; i++) {
  44. 		if (maxV < dist[i]) {
  45. 			maxV = dist[i];
  46. 			ans = i;
  47. 		}
  48. 	}
  49. 	cout << ans << "\n" << maxV;
  50. }
Success #stdin #stdout 0s 5884KB
comments (?)
stdin
copy 
6 10 2
2 6 2
1 4 1
6 1 5
2 5 1
5 1 4
4 5 6
6 2 3
3 5 1
3 1 1
5 2 2
1 2
stdout
copy 
4
8
https://ideone.com/tcB1Mm
language:
C++14 (clang 8.0)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!