fork download
copy 
  1.         // #pragma GCC optimize("Ofast")
  2.         // #pragma GCC optimize ("unroll-loops")
  3.         // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4.  
  5.         #include <bits/stdc++.h>
  6.         #include <ext/pb_ds/assoc_container.hpp> 
  7.         #include <ext/pb_ds/tree_policy.hpp> 
  8.         using namespace std;
  9.         using namespace __gnu_pbds;
  10.  
  11.         typedef long long int ll;
  12.         #define endl '\n'
  13.         #define ld long double
  14.         #define all(a) a.begin(),a.end()
  15.         #define int long long
  16.         #define pb push_back
  17.         #define pii pair <int, int>
  18.         #define ff first
  19.         #define ss second
  20.         #define sz(v) (int)v.size() 
  21.         #define UB upper_bound
  22.         #define LB lower_bound
  23.         #define BP(x) __builtin_popcountll(x)
  24.         #define PQS priority_queue <pii, vector<pii>, greater<pii> > 
  25.         #define OST tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
  26.         mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  27.         int getRand(int l, int r) {
  28.           uniform_int_distribution<int> uid(l, r);
  29.           return uid(rng);
  30.         }
  31.  
  32.         const int INF = 1e9 + 0;
  33.         const int mod = 1e9 + 7;
  34.         //const int mod = 998244353;
  35.         const int N = 2e5 + 5;
  36.  
  37.         int dp[11][11][11][11][11];
  38.         int dist[5][N];
  39.         int p;
  40.         int node[15];
  41.  
  42.         int go(int ind, int a, int b, int c, int d) {
  43.           if(ind > p) return 0;
  44.           int &x = dp[ind][a][b][c][d];
  45.           if(x != -1) return x;
  46.           x = INF;
  47.           if(a > 0) {
  48.             x = min(x, dist[1][node[ind]] + go(ind+1,a-1,b,c,d));
  49.           }
  50.           if(b > 0) {
  51.             x = min(x, dist[2][node[ind]] + go(ind+1,a,b-1,c,d));
  52.           }
  53.           if(c > 0) {
  54.             x = min(x, dist[3][node[ind]] + go(ind+1,a,b,c-1,d));
  55.           }
  56.           if(d > 0) {
  57.             x = min(x, dist[4][node[ind]] + go(ind+1,a,b,c,d-1));
  58.           }
  59.           return x;
  60.         }
  61.  
  62.         void solve() {
  63.           memset(dp,-1,sizeof(dp));
  64.           int n, m;
  65.           cin >> n >> m;
  66.           vector <pii> adj[n+5];
  67.           while(m--) {
  68.             int x, y, w;
  69.             cin >> x >> y >> w;
  70.             adj[x].pb({y,w});
  71.             adj[y].pb({x,w});
  72.           }
  73.           for(int i = 1; i <= 4; i++) {
  74.             for(int j = 1; j <= n; j++) {
  75.               dist[i][j] = INF;
  76.             }
  77.           }
  78.           int k; cin >> k;
  79.           int of[k+2], em[k+2];
  80.           for(int i = 1; i <= k; i++) {
  81.             cin >> of[i] >> em[i];
  82.           }
  83.           cin >> p;
  84.           for(int i = 1; i <= p; i++) {
  85.             cin >> node[i];
  86.           }
  87.           for(int i = 1; i <= k; i++) {
  88.             dist[i][of[i]] = 0;
  89.             PQS Q;
  90.             Q.push({0,of[i]});
  91.             while(!Q.empty()) {
  92.               auto cur = Q.top();
  93.               Q.pop();
  94.               int x = cur.ss, d = cur.ff;
  95.               if(dist[i][x] < d) continue;
  96.               for(auto j : adj[x]) {
  97.                 if(dist[i][j.ff] > d + j.ss) {
  98.                   dist[i][j.ff] = d + j.ss;  
  99.                   Q.push({dist[i][j.ff],j.ff});
  100.                 }
  101.               }
  102.             }
  103.           }
  104.           // cout << "here";
  105.           for(int i = 1; i <= 4; i++) {
  106.             em[i] = max(0ll, em[i]-1);
  107.             em[i] = min(em[i],10ll);
  108.           }
  109.           int ans = go(1,em[1],em[2],em[3],em[4]);
  110.           if(ans >= INF) ans = -1;
  111.           cout << ans << '\n';
  112.         }
  113.  
  114.         signed main() {   
  115.           ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  116.  
  117.           #ifndef ONLINE_JUDGE
  118.            freopen("input.txt", "r", stdin);
  119.           //  freopen("output.txt", "w", stdout);
  120.           #endif
  121.            int t = 1; cin >> t;
  122.            for(int i = 1; i <= t; i++) {
  123.              solve();
  124.           }
  125.         }    
  126.  
  127.         /*
  128.          
  129.         */
Runtime error #stdin #stdout 0.01s 5668KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DHV1E2
language:
C++14 (gcc 8.3)
created:
3 years 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!