Untitled
unknown
plain_text
a year ago
1.7 kB
3
Indexable
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define endl "\n" const double PI = 3.14159265358979; const ll INF = 1e18 + 7; const ll MOD = 1e9 + 7; const ll nax = 2505; const int LOG = 25; vector<ll> dijkstra(ll src, vector<pair<ll, ll> > adj[], ll n) { vector<ll> distance(n + 1, INF); vector<bool> visited(n + 1, false); priority_queue<pair<ll, ll>> pq; distance[src] = 0; pq.push({-distance[src], src}); while(!pq.empty()) { pair<ll, ll> curr = pq.top(); pq.pop(); ll currNode = curr.second; ll currDist = - curr.first; if (visited[currNode]) { continue; } visited[currNode] = true; for (auto &v: adj[currNode]) { ll neigh = v.first; ll wt = v.second; if (distance[neigh] > currDist + wt) { distance[neigh] = distance[currNode] + wt; pq.push({-distance[neigh], neigh}); } } } return distance; } void solve() { ll n, m, u, v, d, src; cin >> n >> m; vector<pair<ll, ll> > adj[n + 1]; for (int i = 1; i <= m; i++) { cin >> u >> v >> d; adj[u].push_back({v, d}); adj[v].push_back({u, d}); } cin >> src; vector<ll> distance = dijkstra(src, adj, n); ll ans = -1; for (int i = 1; i <= n; i++) { for (auto &v : adj[i]) { ll j = v.first; ll l = v.second; ans = max(ans, distance[i] + distance[j] + l); } } cout << ans * 5; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // int t; cin >> t; while(t--) solve(); return 0; }
Editor is loading...
Leave a Comment