ccbeginner

TNFSHOJ 565

Oct 21st, 2020
691
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define SZ(X) (int)(X).size()
  5.  
  6. int n,m,a,b,s;
  7. vector<int> edges[100001];
  8. vector<int> weight[100001];
  9. int ans[100001];
  10. bool vis[100001];
  11.  
  12. struct state{
  13.     int u, cost;
  14.     bool operator>(const state &rhs)const{
  15.         return cost > rhs.cost;
  16.     }
  17. };
  18.  
  19. int32_t main(){
  20.     cin >> n >> m >> a >> b >> s;
  21.     for(int i = 0; i < m; ++i){
  22.         int u,v,w;
  23.         cin >> u >> v >> w;
  24.         edges[u].emplace_back(v);
  25.         edges[v].emplace_back(u);
  26.         weight[u].emplace_back(a+b*w);
  27.         weight[v].emplace_back(a+b*w);
  28.     }
  29.     priority_queue<state, vector<state>, greater<state> > pq;
  30.     state ori = {.u = s, .cost = 0};
  31.     pq.push(ori);
  32.     while(!pq.empty()){
  33.         state tmd = pq.top();
  34.         pq.pop();
  35.         if(vis[tmd.u])continue;
  36.         vis[tmd.u] = 1;
  37.         ans[tmd.u] = tmd.cost;
  38.         for(int i = 0; i < SZ(edges[tmd.u]); ++i){
  39.             state nxt;
  40.             nxt.u = edges[tmd.u][i];
  41.             if(vis[nxt.u])continue;
  42.             nxt.cost = tmd.cost + weight[tmd.u][i];
  43.             pq.push(nxt);
  44.         }
  45.     }
  46.     for(int i = 1; i <= n; ++i){
  47.         cout << ans[i] << ' ';
  48.     }
  49.     cout << '\n';
  50.     return 0;
  51. }
RAW Paste Data