SHARE
TWEET

Untitled

a guest Feb 16th, 2018 121 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //g++ filename.cpp -std=c++14 -DH
  2.  
  3. #ifdef H
  4. #include "/Users/michaelw/stdc++.h"
  5. #else
  6. #include <bits/stdc++.h>
  7. #endif
  8.  
  9. using namespace std;
  10.  
  11. #define pb push_back
  12. #define f first
  13. #define s second
  14. #define lb lower_bound
  15. #define ub upper_bound
  16. #define all(x) x.begin(), x.end()
  17. #define MOD 1e9 + 7
  18.  
  19. typedef long long ll;
  20. typedef pair<int, string> pis;
  21. typedef pair<int,int> pii;
  22.  
  23. struct Edge {
  24.     ll length;
  25.     ll to;
  26. };
  27.  
  28. //set tab size to 3
  29.  
  30. int main(){
  31.     //codeforces cin
  32.     ios_base::sync_with_stdio(false);
  33.     cin.tie(nullptr);
  34.     ifstream fin("filename.in");
  35.     ofstream fout("filename.out");
  36.     ll n, m;
  37.     cin >> n >> m;
  38.     vector<vector<Edge>> graph (n);
  39.     vector<ll> city (n);
  40.     //dist from city i to all cities
  41.     vector<vector<ll>> dist (n);
  42.     for(ll i = 0; i < m; i++){
  43.         ll v, u, w;
  44.         cin >> v >> u >> w;
  45.         Edge e;
  46.         e.to = v-1;
  47.         e.length = w;
  48.         graph[u-1].push_back(e);
  49.         e.to = u-1;
  50.         graph[v-1].push_back(e);
  51.     }
  52.     for(ll i = 0; i < n; i++){
  53.         cin >> city[i];
  54.     }
  55.     for(ll i = 0; i < n; i++){
  56.         dist[i].pb(city[i]);
  57.         for(ll j = 0; j < graph[i].size(); j++){
  58.             // cout << i << " " << graph[i][j].to << " ";
  59.             // cout << city[graph[i][j].to] << " " << graph[i][j].length << endl;
  60.             dist[i].pb(city[graph[i][j].to]+(2*graph[i][j].length));
  61.         }
  62.     }
  63.     for(ll i = 0; i < dist.size(); i++){
  64.         if(i == dist.size()-1) cout << *min_element(dist[i].begin(), dist[i].end()) << endl;
  65.         else cout << *min_element(dist[i].begin(), dist[i].end()) << " ";
  66.     }
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top