fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  3. #define ll long long
  4. #define pii pair<int, int>
  5. #define pb push_back
  6. #define fi first
  7. #define se second
  8. using namespace std;
  9.  
  10. const int M = 250005;
  11. const int N = 505;
  12. const ll INFLL = 1e18+7;
  13.  
  14. struct edges
  15. {
  16.     int u, v, w;
  17. } edge[M];
  18.  
  19. struct songoku
  20. {
  21.     int cost, u, pos;
  22. };
  23.  
  24. int n, m, q;
  25. int lab[N];
  26. pii trace[N];
  27. vector<songoku> g[N];
  28. ll d[N];
  29. bool mark[M];
  30.  
  31. ll calc(queue<pii> q)
  32. {
  33.     while (!q.empty())
  34.     {
  35.         int u=q.front().se, kc=q.front().fi; q.pop();
  36.         if (kc>=u) continue;
  37.  
  38.         for (songoku x : g[u])
  39.         {
  40.             if (d[x.u]>d[u]+x.cost)
  41.             {
  42.                 d[x.u]=d[u]+x.cost;
  43.                 trace[x.u]={u, x.pos};
  44.                 q.push({d[x.u], x.u});
  45.             }
  46.         }
  47.     }
  48.  
  49.     memset(mark, 0, sizeof(mark));
  50.     ll res=0;
  51.     for (int i=1; i<=n; i++)
  52.     {
  53.         int u=i;
  54.         while (trace[u].fi!=0)
  55.         {
  56.             if (mark[trace[u].se]==0) res+=edge[trace[u].se].w;
  57.             mark[trace[u].se]=1;
  58.             u=trace[u].fi;
  59.         }
  60.     }
  61.  
  62.     return res;
  63. }
  64.  
  65. void solve()
  66. {
  67.     cin >> n >> m >> q;
  68.     for (int i=1; i<=m; i++)
  69.     {
  70.         int u, v, w;
  71.         cin >> u >> v >> w;
  72.         edge[i]={u, v, w};
  73.         g[u].pb({w, v, i});
  74.         g[v].pb({w, u, i});
  75.     }
  76.  
  77.     while (q--)
  78.     {
  79.         int k;
  80.         cin >> k;
  81.  
  82.         for (int i=1; i<=n; i++) d[i]=INFLL;
  83.         memset(trace, 0, sizeof(trace));
  84.         queue<pii> q;
  85.         for (int i=1; i<=k; i++)
  86.         {
  87.             int x;
  88.             cin >> x;
  89.             q.push({0, x});
  90.             d[x]=0;
  91.         }
  92.  
  93.         cout << calc(q);
  94.     }
  95. }
  96.  
  97. signed main()
  98. {
  99.     io
  100.     freopen("giaohang.inp","r",stdin);
  101.     freopen("giaohang.out","w",stdout);
  102.  
  103.     solve();
  104. }
Success #stdin #stdout 0.01s 5892KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HRWDj7
language:
C++14 (gcc 8.3)
created:
2 days 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!