fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 5e3+5;
  4. const int mod = 1e9 + 7;
  5. const int oo = 1e18+5;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, pair<int, int>> iii;
  8. #define fi first
  9. #define se second
  10. #define read(_a, n) for(int i = 1; i <= n; i++) cin >> _a[i]
  11. #define For(i, _a, _b) for(int i = _a; i <= _b; i++)
  12. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  13. #define File(_x,_y) if (fopen(_x, "r")) freopen(_x, "r", stdin)//,freopen(_y, "w", stdout)
  14. #define file "main"
  15. #define bit(x, i) ((x >> i) & 1)
  16. #define bat(x, i) (x  (1 << i))
  17.  
  18. int n, m, f[maxn], res = 2e9, d[maxn][maxn], k;
  19. bool check[maxn]; int a[maxn]; int dp[maxn];
  20. vector<ii> adj[maxn];
  21. vector<ii> adj2[maxn];
  22. int b[maxn];
  23.  
  24. void dij(int x)
  25. {
  26.     priority_queue<ii, vector<ii>, greater<ii>> q;
  27.     q.push({0, x});
  28.     for(int i = 1; i <= n; i++) d[x][i] = 2e9;
  29.     d[x][x] = 0;
  30.     while(!q.empty())
  31.     {
  32.         int u = q.top().se; int s = q.top().fi; q.pop();
  33.         for(auto v : adj[u])
  34.         {
  35.             if(d[x][v.fi] > d[x][u] + v.se)
  36.             {
  37.                 d[x][v.fi] = d[x][u] + v.se;
  38.                 q.push({d[x][v.fi], v.fi});
  39.             }
  40.         }
  41.     }
  42. }
  43.  
  44. void bt(int i, int sum, int u)
  45. {
  46.    // cout << i << endl;
  47.     if(i == k+1)
  48.     {
  49.         res = min(res, sum);
  50.       //  cout << sum << " ";
  51.         return ;
  52.     }
  53.     for(auto v : adj2[u])
  54.     {
  55.         if(b[v.fi]) continue;
  56.         b[v.fi] = 1;
  57.         bt(i+1, sum+v.se, v.fi);
  58.         b[v.fi] = 0;
  59.     }
  60. }
  61.  
  62. int32_t main()
  63. {
  64.     fastIO;
  65.     File(file ".inp", file ".out");
  66.     cin >> n >> k >> m;
  67.     int cnt = 0;
  68.     a[1] = 1;
  69.     For(i, 1, k)
  70.     {
  71.         cin >> a[i+1]; check[a[i+1]]=1;
  72.     }
  73.     For(i, 1, m)
  74.     {
  75.         int u, v, s;
  76.         cin >> u >> v >> s;
  77.         adj[u].push_back({v, s});
  78.         adj[v].push_back({u, s});
  79.     }
  80.     for(int u = 1; u <= k+1; u++)
  81.     {
  82.       //  cout << a[u] << " ";
  83.         dij(a[u]);
  84.     }
  85.     for(int u = 1; u <= k+1; u++)
  86.     {
  87.         for(int v = 1; v<= n; v++)
  88.         {
  89.             if(d[a[u]][v] > 0 && d[a[u]][v] != 2e9 && check[v])
  90.             {
  91.                 adj2[a[u]].push_back({v, d[a[u]][v]});
  92.             }
  93.         }
  94.     }
  95.     b[1] = 1;
  96.     bt(1, 0, 1);
  97.     cout << res;
  98. }
  99.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4pOGos
language:
C++14 (clang 8.0)
created:
16 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!